TY - GEN
T1 - Computing minimal spanning subgraphs in linear time
AU - Han, Xiaofeng
AU - Kelsen, Pierre
AU - Ramachandran, Vijaya
AU - Tarjan, Robert
N1 - Funding Information:
*Current affiliation: Zyga Corporation, 28 West Oak Street, Baskingridge, NJ 07920. Research done while he was a graduate student at the Department of Computer Science, Princeton University, Princeton, NJ 08544. tDepartment of Computer Austin, TX 78712; supported 10707. ~Department of Computer Science, Princeton University, Princeton, NJ 08544 and NEC Research Institute, 4 Independence Way, Princeton, NJ 08540. Research at Princeton University partially supported by the National Science Foundation, Grant No. CCR8920505, the Office of Naval Research, Contract No. NOO014-91-J-1463, and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center, Grant No. NSF-STC88-09648.
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 -