Journal article
Efficient Algorithms for k-Terminal Cuts on Planar Graphs
Algorithmica, Vol.38(2), pp.299-316
02/2004
DOI: 10.1007/s00453-003-1061-2
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 min{O(n
2 log n logm), O(m
2
n
1.5 log2
n + k
n)} time algorithm with a (2–2/k)-approximation ratio
(clearly, m \le k). For the case when all k terminals are covered by the boundary of one face of G, we give an
O(n
k3 + (n log n)k
2) 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. To our best knowledge, no previous approximation algorithms specifically
for solving the k-terminal cut problem on planar graphs were known before. The (2–2/k)-approximation
algorithm of Dahlhaus et al. (for general graphs) takes O(k
n
2 log n) time when applied to planar graphs. Our
approximation algorithm for planar graphs runs faster than that of Dahlhaus et al. by at least an O(k/logm)
factor (m \le k).
Details
- Title: Subtitle
- Efficient Algorithms for k-Terminal Cuts on Planar Graphs
- Creators
- Danny Z Chen - University of Notre DameXiadong Wu - Department of Computer Science, University of Texas – Pan American, 1201 West University Drive, Edinburg, TX 78539 USA
- Resource Type
- Journal article
- Publication Details
- Algorithmica, Vol.38(2), pp.299-316
- Publisher
- Springer-Verlag
- DOI
- 10.1007/s00453-003-1061-2
- ISSN
- 0178-4617
- eISSN
- 1432-0541
- Language
- English
- Date published
- 02/2004
- Academic Unit
- Electrical and Computer Engineering; Radiation Oncology; The Iowa Institute for Biomedical Imaging
- Record Identifier
- 9984196962502771
Metrics
10 Record Views