Computing Minimal Spanning Subgraphs in Linear Time

DOI10.1137/S0097539791224509zbMath0841.05084OpenAlexW1965471351MaRDI QIDQ4862800

Pierre Kelsen, Vijaya Ramachandran, Xiaofeng Han, Robert Endre 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

complexityparallel algorithmsdigraphsworst-case complexityspanning treesmonotone propertylinear algorithm2-edge-connectivity\(P\)-graphstrongly connected spanning subgraphcollapsing cyclescontracting chains

Mathematics Subject Classification ID

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

Related Items (1)

On the (di)graphs with (directed) proper connection number two

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