TY - GEN
T1 - Approximate minimum cuts and their enumeration
AU - Beideman, Calvin
AU - Chandrasekaran, Karthekeyan
AU - Wang, Weihang
N1 - Supported in part by NSF grants CCF-1814613 and CCF-1907937.
PY - 2023
Y1 - 2023
N2 - 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 ⌊2α⌋ + 1. This leads to an alternative proof that the number of α-approximate minimum cuts in a n-vertex connected graph is nO(α) and they can all be enumerated in deterministic polynomial time for constant α.
AB - 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 ⌊2α⌋ + 1. This leads to an alternative proof that the number of α-approximate minimum cuts in a n-vertex connected graph is nO(α) and they can all be enumerated in deterministic polynomial time for constant α.
UR - http://www.scopus.com/inward/record.url?scp=85190289636&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85190289636&partnerID=8YFLogxK
U2 - 10.1137/1.9781611977585.ch4
DO - 10.1137/1.9781611977585.ch4
M3 - Conference contribution
AN - SCOPUS:85190289636
T3 - Proceedings - 2023 SIAM Symposium on Simplicity in Algorithms, SOSA 2023
SP - 36
EP - 41
BT - Proceedings - 2023 SIAM Symposium on Simplicity in Algorithms, SOSA 2023
A2 - Kavitha, Telikepalli
A2 - Mehlhorn, Kurt
PB - Society for Industrial and Applied Mathematics Publications
T2 - 2023 SIAM Symposium on Simplicity in Algorithms, SOSA 2023
Y2 - 23 January 2023 through 25 January 2023
ER -