Polynomial time approximation schemes for maxbisection on planar and geometric graphs
(2005) In SIAM Journal on Computing 35(1). p.110119 Abstract
 The maxbisection and minbisection 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 maxbisection problem on arbitrary planar graphs solving a longstanding open problem. The method of solution involves designing exact polynomial time algorithms for computing optimal partitions of bounded treewidth graphs, in particular max and minbisection, which could be of independent interest. Using a similar method we design also the first polynomial time approximation scheme for maxbisection on unit disk graphs ( which could also be easily extended to... (More)
 The maxbisection and minbisection 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 maxbisection problem on arbitrary planar graphs solving a longstanding open problem. The method of solution involves designing exact polynomial time algorithms for computing optimal partitions of bounded treewidth graphs, in particular max and minbisection, which could be of independent interest. Using a similar method we design also the first polynomial time approximation scheme for maxbisection 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:
http://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, NPhardness, approximation algorithms
 in
 SIAM Journal on Computing
 volume
 35
 issue
 1
 pages
 110  119
 publisher
 SIAM Publications
 external identifiers

 wos:000232561400005
 scopus:33644603112
 ISSN
 00975397
 DOI
 10.1137/S009753970139567X
 project
 VR 20024049
 language
 English
 LU publication?
 yes
 id
 97428ca8276a4de4afcc7e5dbdaf8c54 (old id 216779)
 date added to LUP
 20070822 10:50:46
 date last changed
 20171001 04:34:03
@article{97428ca8276a4de4afcc7e5dbdaf8c54, abstract = {The maxbisection and minbisection 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 maxbisection problem on arbitrary planar graphs solving a longstanding open problem. The method of solution involves designing exact polynomial time algorithms for computing optimal partitions of bounded treewidth graphs, in particular max and minbisection, which could be of independent interest. Using a similar method we design also the first polynomial time approximation scheme for maxbisection 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 = {00975397}, keyword = {graph bisection,planar graphs,combinatorial optimization,polynomial time approximation schemes,NPhardness,approximation algorithms}, language = {eng}, number = {1}, pages = {110119}, publisher = {SIAM Publications}, series = {SIAM Journal on Computing}, title = {Polynomial time approximation schemes for maxbisection on planar and geometric graphs}, url = {http://dx.doi.org/10.1137/S009753970139567X}, volume = {35}, year = {2005}, }