Smallest Augmentations to Biconnect a Graph

DOI10.1137/0206003MaRDI QIDQ4121936zbMATH OpenOpenAlexFDO

Authors 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

(20)

• Edge-connectivity augmentation problems
• On the relationship between the biconnectivity augmentation and traveling salesman problems
• A minimum 3-connectivity augmentation of a graph
• Triangulating planar graphs while minimizing the maximum degree
• A smallest augmentation to 3-connect a graph
• A unified framework for bi(tri)connectivity and chordal augmentation
• 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 polyhedral approach to planar augmentation and related problems
• Optimal bi-level augmentation for selective! enhancing graph connectivity with applications
• Optimal augmentation for bipartite componentwise biconnectivity in linear time
• Undirected vertex-connectivity structure and smallest four-vertex-connectivity augmentation (extended abstract)
• Augmenting the edge connectivity of planar straight line graphs to three
• On the constrained Steiner strong connectivity augmentation problem
• Distributed graph augmentation protocols to achieve strong connectivity in multi-agent networks
• How to allocate review tasks for robust ranking
• Smallest bipartite bridge-connectivity augmentation
• The bridge-connectivity augmentation problem with a partition constraint

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)