The 2‐connected Steiner subgraph problem is that of finding a minimum‐weight 2‐connected subgraph that spans a subset of distinguished vertices. This paper presents linear‐time algorithms for solving the 2‐connected Steiner subgraph problem on two special classes of graphs, W 4 ‐free graphs and Halin graphs. Although different in detail, the algorithms adopt a common strategy exploiting known decompositions. As a special case, the algorithms also solve the Traveling Salesman Problem on W 4 ‐free graphs and Halin graphs.
No takes yet. Share an insight, caveat, or question.
Coullard et al. (1993) studied this question.
Synapse has enriched 3 closely related papers on similar clinical questions. Consider them for comparative context: