Polynomial time approximation schemes for max-bisection on planar and geometric graphs
(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:
https://lup.lub.lu.se/record/216779
- author
- Jansen, K ; Karpinski, M ; Lingas, Andrzej LU and Seidel, E
- organization
- publishing date
- 2005
- 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
- Society for Industrial and Applied Mathematics
- 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
- 2016-04-01 15:22:38
- date last changed
- 2022-03-30 00:58:58
@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}},
keywords = {{graph bisection; planar graphs; combinatorial optimization; polynomial time approximation schemes; NP-hardness; approximation algorithms}},
language = {{eng}},
number = {{1}},
pages = {{110--119}},
publisher = {{Society for Industrial and Applied Mathematics}},
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}},
doi = {{10.1137/S009753970139567X}},
volume = {{35}},
year = {{2005}},
}