On finding two-connected subgraphs in planar graphs

On finding two-connected subgraphs in planar graphs

0.00 Avg rating—0 Votes
Article ID: iaor19982359
Country: Netherlands
Volume: 20
Issue: 2
Start Page Number: 81
End Page Number: 84
Publication Date: Feb 1997
Journal: Operations Research Letters
Authors:
Abstract:

We consider a basic problem in the design of reliable networks, namely, that of finding a minimum-weight 2-connected subgraph spanning a given set K of vertices in a planar graph. We show a relationship between this problem and that of finding shortest trails and cycles enclosing K, and derive a polynomial-time algorithm in the case when the vertices of K all lie on the same face.

Reviews

Required fields are marked *. Your email address will not be published.