Computing minimal spanning subgraphs in linear time

Xiaofeng Han, Pierre Kelsen, Vijaya Ramachandran, Robert Tarjan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992
PublisherAssociation for Computing Machinery
Pages146-156
Number of pages11
ISBN (Electronic)089791466X
StatePublished - Sep 1 1992
Event3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992 - Orlando, United States
Duration: Jan 27 1992Jan 29 1992

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
VolumePart F129721

Other

Other3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992
CountryUnited States
CityOrlando
Period1/27/921/29/92

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Computing minimal spanning subgraphs in linear time'. Together they form a unique fingerprint.

  • Cite this

    Han, X., Kelsen, P., Ramachandran, V., & Tarjan, R. (1992). Computing minimal spanning subgraphs in linear time. In Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms. SODA 1992 (pp. 146-156). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. Part F129721). Association for Computing Machinery.