Book chapter
Efficient Algorithms for k-Terminal Cuts on Planar Graphs
Algorithms and Computation, pp.332-344
Lecture Notes in Computer Science, Springer Berlin Heidelberg
12/04/2001
DOI: 10.1007/3-540-45678-3_29
Abstract
The minimum k-terminal cut problem is of considerable theoretical interest and arises in several applied areas such as parallel and distributed computing, VLSI circuit design, and networking. In this paper, we present two new approximation and exact algorithms for this problem on an n-vertex undirected weighted planar graph G. For the case when the k terminals are covered by the boundaries of m > 1 faces of G, we give a minOn2 log n log m, O(m2n1.5 log2 n+kn) time algorithm with a (2 . 2k )-approximation ratio (clearly, m k). For the case when all k terminals are covered by the boundary of one face of G, we give an O(nk3 +(n log n)k2) time exact algorithm, or a linear time exact algorithm if k = 3, for computing an optimal k-terminal cut. Our algorithms are based on interesting observations and improve the previous algorithms when they are applied to planar graphs.
Details
- Title: Subtitle
- Efficient Algorithms for k-Terminal Cuts on Planar Graphs
- Creators
- Danny Z Chen - University of Notre DameXiaodong Wu - University of Notre Dame
- Resource Type
- Book chapter
- Publication Details
- Algorithms and Computation, pp.332-344
- Publisher
- Springer Berlin Heidelberg; Berlin, Heidelberg
- Series
- Lecture Notes in Computer Science
- DOI
- 10.1007/3-540-45678-3_29
- eISSN
- 1611-3349
- ISSN
- 0302-9743
- Language
- English
- Date published
- 12/04/2001
- Academic Unit
- Electrical and Computer Engineering; Radiation Oncology; The Iowa Institute for Biomedical Imaging
- Record Identifier
- 9984197318302771
Metrics
15 Record Views