Advanced

Polynomial time approximation schemes for max-bisection on planar and geometric graphs

Jansen, K; Karpinski, M; Lingas, Andrzej LU and Seidel, E (2005) In SIAM Journal on Computing 35(1). p.110-119
Abstract
The max-bisection and min-bisection problems are to find a partition of the vertices of a graph into two equal size subsets that, respectively, maximizes or minimizes the number of edges with endpoints in both subsets. We design the first polynomial time approximation scheme for the max-bisection problem on arbitrary planar graphs solving a long-standing open problem. The method of solution involves designing exact polynomial time algorithms for computing optimal partitions of bounded treewidth graphs, in particular max- and min-bisection, which could be of independent interest. Using a similar method we design also the first polynomial time approximation scheme for max-bisection on unit disk graphs ( which could also be easily extended to... (More)
The max-bisection and min-bisection problems are to find a partition of the vertices of a graph into two equal size subsets that, respectively, maximizes or minimizes the number of edges with endpoints in both subsets. We design the first polynomial time approximation scheme for the max-bisection problem on arbitrary planar graphs solving a long-standing open problem. The method of solution involves designing exact polynomial time algorithms for computing optimal partitions of bounded treewidth graphs, in particular max- and min-bisection, which could be of independent interest. Using a similar method we design also the first polynomial time approximation scheme for max-bisection on unit disk graphs ( which could also be easily extended to other geometrically defined graphs). (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
graph bisection, planar graphs, combinatorial optimization, polynomial time approximation schemes, NP-hardness, approximation algorithms
in
SIAM Journal on Computing
volume
35
issue
1
pages
110 - 119
publisher
SIAM Publications
external identifiers
  • wos:000232561400005
  • scopus:33644603112
ISSN
0097-5397
DOI
10.1137/S009753970139567X
project
VR 2002-4049
language
English
LU publication?
yes
id
97428ca8-276a-4de4-afcc-7e5dbdaf8c54 (old id 216779)
date added to LUP
2007-08-22 10:50:46
date last changed
2017-10-01 04:34:03
@article{97428ca8-276a-4de4-afcc-7e5dbdaf8c54,
  abstract     = {The max-bisection and min-bisection problems are to find a partition of the vertices of a graph into two equal size subsets that, respectively, maximizes or minimizes the number of edges with endpoints in both subsets. We design the first polynomial time approximation scheme for the max-bisection problem on arbitrary planar graphs solving a long-standing open problem. The method of solution involves designing exact polynomial time algorithms for computing optimal partitions of bounded treewidth graphs, in particular max- and min-bisection, which could be of independent interest. Using a similar method we design also the first polynomial time approximation scheme for max-bisection on unit disk graphs ( which could also be easily extended to other geometrically defined graphs).},
  author       = {Jansen, K and Karpinski, M and Lingas, Andrzej and Seidel, E},
  issn         = {0097-5397},
  keyword      = {graph bisection,planar graphs,combinatorial optimization,polynomial time approximation schemes,NP-hardness,approximation algorithms},
  language     = {eng},
  number       = {1},
  pages        = {110--119},
  publisher    = {SIAM Publications},
  series       = {SIAM Journal on Computing},
  title        = {Polynomial time approximation schemes for max-bisection on planar and geometric graphs},
  url          = {http://dx.doi.org/10.1137/S009753970139567X},
  volume       = {35},
  year         = {2005},
}