Approximate minimum cuts and their enumeration

November 30, 2022 Β· Declared Dead Β· πŸ› SIAM Symposium on Simplicity in Algorithms

πŸ‘» CAUSE OF DEATH: Ghosted
No code link whatsoever

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Calvin Beideman, Karthekeyan Chandrasekaran, Weihang Wang arXiv ID 2211.16747 Category cs.DS: Data Structures & Algorithms Citations 4 Venue SIAM Symposium on Simplicity in Algorithms Last Checked 4 months ago
Abstract
We show that every $Ξ±$-approximate minimum cut in a connected graph is the unique minimum $(S,T)$-terminal cut for some subsets $S$ and $T$ of vertices each of size at most $\lfloor2Ξ±\rfloor+1$. This leads to an alternative proof that the number of $Ξ±$-approximate minimum cuts in a $n$-vertex connected graph is $n^{O(Ξ±)}$ and they can all be enumerated in deterministic polynomial time for constant $Ξ±$.
Community shame:
Not yet rated
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

πŸ“œ Similar Papers

In the same crypt β€” Data Structures & Algorithms

Died the same way β€” πŸ‘» Ghosted