Finding a Smallest Augmentation to Biconnect a Graph

DOI10.1137/0222056zbMath0782.68051OpenAlexW2015645763MaRDI QIDQ3142584

Tsan-sheng Hsu, Vijaya Ramachandran

Publication date: 4 January 1994

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

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

zbMATH Keywords

graph augmentationEREW PRAMlinear-time algorithmbiconnected graphpoly-log time

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Applications of graph theory to circuits and networks (94C15) Connectivity (05C40)

Related Items

Augmenting weighted graphs to establish directed point-to-point connectivity ⋮ Smallest bipartite bridge-connectivity augmentation ⋮ Tri-connectivity augmentation in trees ⋮ On the Hardness and Approximability of Planar Biconnectivity Augmentation ⋮ 5-Shredders of Contraction-Critical 5-Connected Graphs ⋮ An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach ⋮ Optimal bi-level augmentation for selective! enhancing graph connectivity with applications ⋮ Augmenting the edge connectivity of planar straight line graphs to three ⋮ Multigraph augmentation under biconnectivity and general edge-connectivity requirements ⋮ Graph connectivity and its augmentation: Applications of MA orderings ⋮ How to allocate review tasks for robust ranking ⋮ Triangulating planar graphs while minimizing the maximum degree