Local edge-connectivity augmentation in hypergraphs is NP-complete

DOI10.1016/J.DAM.2009.12.011zbMath1225.05191OpenAlexW2072785948MaRDI QIDQ968204

Ben Cosh, Zoltán Király, Bill Jackson

Publication date: 5 May 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2009.12.011

zbMATH Keywords

NP-completenesshypergraphsedge-connectivity augmentation

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (7)

The Generalized Terminal Backup Problem ⋮ A New Approach to Splitting-Off ⋮ Edge-Connectivity Augmentations of Graphs and Hypergraphs ⋮ A unifying approach to splitting-off ⋮ Augmenting the Edge‐Connectivity of a Hypergraph by Adding a Multipartite Graph ⋮ Sufficient conditions for maximally edge-connected hypergraphs ⋮ Approximation algorithms for connectivity augmentation problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Covering symmetric supermodular functions by uniform hypergraphs
• Edge-connectivity augmentation problems
• Augmenting hypergraphs by edges of size two
• Covering symmetric supermodular functions by graphs
• Hypergraph connectivity augmentation
• Successive edge-connectivity augmentation problems
• On the minimum local-vertex-connectivity augmentation in graphs
• Independence free graphs and vertex connectivity augmentation
• Minimal edge-coverings of pairs of sets
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• Detachments Preserving Local Edge-Connectivity of Graphs
• Combinatorial optimization. Theory and algorithms

This page was built for publication: Local edge-connectivity augmentation in hypergraphs is NP-complete