A Deterministic Algorithm for Finding All Minimum k‐Way Cuts
Authors:
- Yoko KamidoiYKYoko Kamidoi
- Noriyoshi YoshidaNYNoriyoshi Yoshida
- Hiroshi NagamochiHNHiroshi Nagamochi
- 1 January 2007
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 36 (5) , 1329-1341
Abstract
Let $G=(V,E)$ be an edge‐weighted undirected graph with n vertices and m edges. We present a deterministic algorithm to compute a minimum k‐way cut of G for a given k. Our algorithm is a divide‐and‐conquer method based on a procedure that reduces an instance of the minimum k‐way cut problem to $O(n^{2k-5})$ instances of the minimum $(\lfloor (k+\sqrt{k})/2\rfloor+1)$‐way cut problem, and can be implemented to run in $O(n^{4k/(1-1.71/\sqrt{k}) -31} )$ time. With a slight modification, the algorithm can find all minimum k‐way cuts in $O(n^{4k/(1-1.71/\sqrt{k}) -16} )$ time.
Keywords
This publication has 34 references indexed in Scilit:
- Analysis of LP relaxations for multiway and multicut problemsNetworks, 1999
- Recent directions in netlist partitioning: a surveyIntegration, 1995
- A Faster Algorithm for Finding the Minimum Cut in a Directed GraphJournal of Algorithms, 1994
- The Complexity of Multiterminal CutsSIAM Journal on Computing, 1994
- A Polynomial Algorithm for the k-cut Problem for Fixed kMathematics of Operations Research, 1994
- Minimum Path BasesJournal of Algorithms, 1993
- A new approach to the maximum-flow problemJournal of the ACM, 1988
- Optimal attack and reinforcement of a networkJournal of the ACM, 1985
- On finding the K best cuts in a networkOperations Research Letters, 1984
- Connectivity and edge-disjoint spanning treesInformation Processing Letters, 1983