1. A DETERMINISTIC ALGORITHM FOR FINDING ALL MINIMUM k-WAY CUTS.
- Author
-
Kamidoi, Yoko, Yoshida, Noriyoshi, and Nagamochi, Hiroshi
- Subjects
- *
ALGORITHMS , *FOUNDATIONS of arithmetic , *MATHEMATICAL analysis , *MATHEMATICAL models , *COMPUTER systems , *MONTE Carlo method - 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(n2k-5) instances of the minimum (⌊(k + √k)/2⌋ + 1)-way cut problem, and can be implemented to run in O(n4k/(1–1.71/√k)-31) time. With a slight modification, the algorithm can find all minimum k-way cuts in O(n4k/(1–1.71/√k)-16) time. [ABSTRACT FROM AUTHOR]
- Published
- 2006
- Full Text
- View/download PDF