Computing Minimal Spanning Subgraphs in Linear Time

DOI10.1137/S0097539791224509MaRDI QIDQ4862800zbMATH OpenOpenAlexFDO

Authors Xiaofeng Han, Pierre Kelsen, Vijaya Ramachandran, Robert E. Tarjan

Publication date 14 July 1996

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0097539791224509

zbMATH Keywords

spanning treescomplexitydigraphsparallel algorithmsworst-case complexitymonotone propertylinear algorithm2-edge-connectivity\(P\)-graphstrongly connected spanning subgraphcollapsing cyclescontracting chains

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40)

Recommendations

• scientific article; zbMATH DE number 742959
• A linear time algorithm for the bottleneck biconnected spanning subgraph problem
• On Finding Minimal Two-Connected Subgraphs
• Faster algorithms for computing maximal 2-connected subgraphs in sparse directed graphs
• Biconnectivity approximations and graph carvings

Cited in

(7)

• On the (di)graphs with (directed) proper connection number two
• A Linear-Time Algorithm for Finding a Complete Graph Minor in a Dense Graph
• scientific article; zbMATH DE number 742959 (Why is no real title available?)
• On Finding Minimal Two-Connected Subgraphs
• Linear time algorithms for graph search and connectivity determination on complement graphs.
• Linear algorithm for selecting an almost regular spanning subgraph in an almost regular graph
• Minmax strongly connected subgraphs with node penalties

This page was built for publication: Computing Minimal Spanning Subgraphs in Linear Time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4862800)