Local edge-connectivity augmentation in hypergraphs is NP-complete

DOI10.1016/J.DAM.2009.12.011MaRDI QIDQ968204zbMATH OpenOpenAlexFDO

Authors Zoltán Király, Ben Cosh, 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

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

Recommendations

• Edge-augmentation of hypergraphs
• Graph-Theoretic Concepts in Computer Science
• Augmenting the edge-connectivity of a hypergraph by adding a multipartite graph
• Augmenting the edge-connectivity of a hypergraph by adding a multipartite graph
• On the minimum local-vertex-connectivity augmentation in graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Approximating connectivity augmentation problems
• Augmenting Graphs to Meet Edge-Connectivity Requirements
• Augmenting hypergraphs by edges of size two
• Combinatorial optimization. Theory and algorithms
• Covering symmetric supermodular functions by graphs
• Covering symmetric supermodular functions by uniform hypergraphs
• Detachments Preserving Local Edge-Connectivity of Graphs
• Edge-connection of graphs, digraphs, and hypergraphs
• Edge-connectivity augmentation problems
• Hypergraph connectivity augmentation
• Independence free graphs and vertex connectivity augmentation
• Minimal edge-coverings of pairs of sets
• On the minimum local-vertex-connectivity augmentation in graphs
• Successive edge-connectivity augmentation problems

Cited in

(9)

• A New Approach to Splitting-Off
• Sufficient conditions for maximally edge-connected hypergraphs
• The generalized terminal backup problem
• Edge-connectivity augmentations of~graphs~and~hypergraphs
• Approximation algorithms for connectivity augmentation problems
• A unifying approach to splitting-off
• scientific article; zbMATH DE number 2080985 (Why is no real title available?)
• Approximation algorithms for node and element connectivity augmentation problems
• Augmenting the edge-connectivity of a hypergraph by adding a multipartite graph

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

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