Smallest Augmentations to Biconnect a Graph

DOI10.1137/0206003zbMATH Open0352.05048OpenAlexW1965920734MaRDI QIDQ4121936FDOQ4121936

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)

Cited In (18)

• Smallest bipartite bridge-connectivity augmentation
• A unified framework for bi(tri)connectivity and chordal augmentation
• A minimum 3-connectivity augmentation of a graph
• How to allocate review tasks for robust ranking
• Triangulating planar graphs while minimizing the maximum degree
• The bridge-connectivity augmentation problem with a partition constraint
• Kernelization and complexity results for connectivity augmentation problems
• Undirected vertex-connectivity structure and smallest four-vertex-connectivity augmentation (extended abstract)
• Optimal bi-level augmentation for selective! enhancing graph connectivity with applications
• A smallest augmentation to 3-connect a graph
• On triangulating planar graphs under the four-connectivity constraint
• Triangulating planar graphs while minimizing the maximum degree
• Optimal augmentation for bipartite componentwise biconnectivity in linear time
• Approximation algorithms for graph augmentation
• Edge-connectivity augmentation problems
• On the relationship between the biconnectivity augmentation and traveling salesman problems
• A polyhedral approach to planar augmentation and related problems
• Augmenting the edge connectivity of planar straight line graphs to three

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

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