A minimum 3-connectivity augmentation of a graph

DOI10.1016/0022-0000(93)90050-7zbMath0768.68188OpenAlexW2038041864MaRDI QIDQ1208926

S. Singh

Publication date: 16 May 1993

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(93)90050-7

zbMATH Keywords

algorithmNP- completeundirected simple graphminimum 3-connectivity augmentation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Smallest bipartite bridge-connectivity augmentation ⋮ Triangulating planar graphs while minimizing the maximum degree ⋮ How to make a strongly connected digraph two-connected ⋮ A polyhedral approach to planar augmentation and related problems ⋮ Multigraph augmentation under biconnectivity and general edge-connectivity requirements ⋮ An approximation algorithm for minimum-cost vertex-connectivity problems ⋮ Graph connectivity and its augmentation: Applications of MA orderings ⋮ Independence free graphs and vertex connectivity augmentation ⋮ The bridge-connectivity augmentation problem with a partition constraint ⋮ A smallest augmentation to 3-connect a graph ⋮ Algorithm and complexity of the two disjoint connected dominating sets problem on trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Edge-connectivity augmentation problems
• A smallest augmentation to 3-connect a graph
• Approximation Algorithms for Several Graph Augmentation Problems
• Augmentation Problems
• Smallest Augmentations to Biconnect a Graph
• `` Strong NP-Completeness Results
• Dividing a Graph into Triconnected Components