Random contractions and sampling for hypergraph and hedge connectivity

DOI10.1137/1.9781611974782.71MaRDI QIDQ4575812zbMATH OpenOpenAlexFDO

Authors Mohsen Ghaffari, Debmalya Panigrahi, David R. Karger

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611974782.71

Mathematics Subject Classification ID

Connectivity (05C40) Hypergraphs (05C65) Graph algorithms (graph-theoretic aspects) (05C85) Reliability, testing and fault tolerance of networks and computer systems (68M15)

Recommendations

• Hypergraph \(k\)-cut in randomized polynomial time
• Minimum cut and minimum k-cut in hypergraphs via branching contractions
• scientific article; zbMATH DE number 6850403
• Random sampling in cut, flow, and network design problems
• Random sampling in cut, flow, and network design problems

Cited in

(16)

• Faster connectivity in low-rank hypergraphs via expander decomposition
• Minimum label \(s\)-\(t\) cut has large integrality gaps
• Hypergraph \(k\)-cut in randomized polynomial time
• Multicriteria cuts and size-constrained \(k\)-cuts in hypergraphs
• Minimum cuts and sparsification in hypergraphs
• Tight Bounds on Vertex Connectivity Under Sampling
• On random sampling in uniform hypergraphs
• Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
• Minimum Cut and Minimum k -Cut in Hypergraphs via Branching Contractions
• Multicriteria Cuts and Size-Constrained k-Cuts in Hypergraphs.
• Deterministic enumeration of all minimum cut-sets and k-cut-sets in hypergraphs for fixed k
• Splitting-off in hypergraphs
• Splitting-off in hypergraphs
• Shortest cycles with monotone submodular costs
• Hypergraph connectivity augmentation in strongly polynomial time
• Connectivity labeling in faulty colored graphs

This page was built for publication: Random contractions and sampling for hypergraph and hedge connectivity

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