TY - GEN

T1 - Computing minimal spanning subgraphs in linear time

AU - Han, Xiaofeng

AU - Kelsen, Pierre

AU - Ramachandran, Vijaya

AU - Tarjan, Robert

PY - 1992/9/1

Y1 - 1992/9/1

N2 - Let P be a property of undirected graphs. We consider the following problem: given a graph G that has property P, find a minimal spanning subgraph of G with property P. We describe two related algorithms for this problem and prove their correctness under some rather weak assumptions about P. We devise a general technique for analyzing the worst-case behavior of these algorithms. By applying the technique to 2-edge-connectivity and biconnectivity, we obtain an ω(m + n log n) lower bound on the worst-case running time of the algorithms for these two properties, thus settling open questions posed earlier with regard to these properties. We then describe refinements of the basic algorithms that yield the first linear-time algorithms for finding a minimal 2-edge-connected spanning subgraph and a minimal biconnected spanning subgraph of a graph.

AB - Let P be a property of undirected graphs. We consider the following problem: given a graph G that has property P, find a minimal spanning subgraph of G with property P. We describe two related algorithms for this problem and prove their correctness under some rather weak assumptions about P. We devise a general technique for analyzing the worst-case behavior of these algorithms. By applying the technique to 2-edge-connectivity and biconnectivity, we obtain an ω(m + n log n) lower bound on the worst-case running time of the algorithms for these two properties, thus settling open questions posed earlier with regard to these properties. We then describe refinements of the basic algorithms that yield the first linear-time algorithms for finding a minimal 2-edge-connected spanning subgraph and a minimal biconnected spanning subgraph of a graph.

UR - http://www.scopus.com/inward/record.url?scp=0013361622&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0013361622&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0013361622

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 146

EP - 156

BT - Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992

PB - Association for Computing Machinery

T2 - 3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992

Y2 - 27 January 1992 through 29 January 1992

ER -