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:
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, NPhardness, 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
 00975397
 DOI
 10.1137/S009753970139567X
 project
 VR 20024049
 language
 English
 LU publication?
 yes
 id
 97428ca8276a4de4afcc7e5dbdaf8c54 (old id 216779)
 date added to LUP
 20160401 15:22:38
 date last changed
 20210217 01:53:51
@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}, language = {eng}, number = {1}, pages = {110119}, publisher = {Society for Industrial and Applied Mathematics}, 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}, doi = {10.1137/S009753970139567X}, volume = {35}, year = {2005}, }