Linear‐time algorithms for the 2‐connected steiner subgraph problem on special classes of graphs
Collette R. Coullard, Abdur Rais, Ronald L. Rardin, Donald K. Wagner · Networks · 1993
Abstract 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, W4‐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 W4‐free graphs and Halin graphs. © 1993 by John Wiley & Sons, Inc.