Random Contractions and Sampling for Hypergraph and Hedge Connectivity

DOI10.1137/1.9781611974782.71zbMath1410.05202OpenAlexW2922372630MaRDI QIDQ4575812

Debmalya Panigrahi, Mohsen Ghaffari, 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

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

Related Items (8)

Minimum Cuts and Sparsification in Hypergraphs ⋮ Faster connectivity in low-rank hypergraphs via expander decomposition ⋮ Minimum Cut and Minimum k -Cut in Hypergraphs via Branching Contractions ⋮ Multicriteria cuts and size-constrained \(k\)-cuts in hypergraphs ⋮ 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. ⋮ Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time

This page was built for publication: Random Contractions and Sampling for Hypergraph and Hedge Connectivity