Linear-time Algorithms for the 2-connected Steiner Subgraph Problem On Special Classes of Graphs

Coullard, CR.;Rais, Abdur;Rardin, RL.;Wagner, DK.
(1993) Networks (New York) : an international journal — Vol. 23, n° 3, p. 195-206 (1993)

Files

No attached file found for this publication.

Details

Authors
  • Coullard, CR.
    Author
  • Rais, AbdurUCLouvain
    Author
  • Rardin, RL.
    Author
  • Wagner, DK.
    Author
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.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Coullard, CR., Rais, A., Rardin, RL., & Wagner, DK. (1993). Linear-time Algorithms for the 2-connected Steiner Subgraph Problem On Special Classes of Graphs. Networks (New York) : an international journal, 23(3), 195-206. https://doi.org/10.1002/net.3230230307 (Original work published 1993)