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

(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)
• A smallest augmentation to 3-connect a graph
• Optimal bi-level augmentation for selective! enhancing graph connectivity with applications
• On triangulating planar graphs under the four-connectivity constraint
• Triangulating planar graphs while minimizing the maximum degree
• Edge-connectivity augmentation problems
• On the relationship between the biconnectivity augmentation and traveling salesman problems
• Approximation algorithms for graph augmentation
• Optimal augmentation for bipartite componentwise biconnectivity in linear time
• 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)