Computing Minimal Spanning Subgraphs in Linear Time
DOI10.1137/S0097539791224509zbMATH Open0841.05084OpenAlexW1965471351MaRDI QIDQ4862800FDOQ4862800
Pierre Kelsen, Vijaya Ramachandran, Robert E. Tarjan, Xiaofeng Han
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
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
spanning treescomplexitydigraphsparallel algorithmsworst-case complexitymonotone propertylinear algorithm2-edge-connectivity\(P\)-graphstrongly connected spanning subgraphcollapsing cyclescontracting chains
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40)
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
- Title not available (Why is that?)
- 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)
