Smallest Augmentations to Biconnect a Graph

DOI10.1137/0206003zbMath0352.05048OpenAlexW1965920734MaRDI QIDQ4121936

Arnie Rosenthal, Anita Goldner

Publication date: 1977

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

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

Mathematics Subject Classification ID

Graph theory (05C99) Algorithms in computer science (68W99)

Related Items (16)

Smallest bipartite bridge-connectivity augmentation ⋮ Edge-connectivity augmentation problems ⋮ Triangulating planar graphs while minimizing the maximum degree ⋮ A polyhedral approach to planar augmentation and related problems ⋮ Optimal bi-level augmentation for selective! enhancing graph connectivity with applications ⋮ On the relationship between the biconnectivity augmentation and traveling salesman problems ⋮ Augmenting the edge connectivity of planar straight line graphs to three ⋮ A minimum 3-connectivity augmentation of a graph ⋮ How to allocate review tasks for robust ranking ⋮ The bridge-connectivity augmentation problem with a partition constraint ⋮ Kernelization and complexity results for connectivity augmentation problems ⋮ Triangulating planar graphs while minimizing the maximum degree ⋮ On triangulating planar graphs under the four-connectivity constraint ⋮ Approximation algorithms for graph augmentation ⋮ A smallest augmentation to 3-connect a graph ⋮ A UNIFIED FRAMEWORK FOR BI(TRI)CONNECTIVITY AND CHORDAL AUGMENTATION

This page was built for publication: Smallest Augmentations to Biconnect a Graph