Advanced

Approximation algorithms for MAX-BISECTION on low degree regular graphs

Karpinski, M; Kowaluk, M and Lingas, Andrzej LU (2004) In Fundamenta Informaticae 62(3-4). p.369-375
Abstract
The max-bisection problem is to find a partition of the vertices of a graph into two equal size subsets that maximizes the number of edges with endpoints in both subsets. We obtain new improved approximation ratios for the max-bisection problem on the low degree k-regular graphs for 3 less than or equal to k less than or equal to 8, by deriving some improved transformations from a maximum cut intofrom a maximum bisection. In the case of three regular graphs we obtain an approximation ratio of 0.854, and in the case of four and five regular graphs, approximation ratios of 0.805, and 0.812, respectively.
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, approximation algorithms, regular graphs
in
Fundamenta Informaticae
volume
62
issue
3-4
pages
369 - 375
publisher
IOS Press
external identifiers
  • wos:000225994200005
  • scopus:24044459262
ISSN
0169-2968
project
VR 2002-4049
language
English
LU publication?
yes
id
be1ad839-a1e4-4ac8-96fd-9963fc827f76 (old id 257989)
date added to LUP
2007-08-02 16:21:44
date last changed
2017-01-01 07:13:56
@article{be1ad839-a1e4-4ac8-96fd-9963fc827f76,
  abstract     = {The max-bisection problem is to find a partition of the vertices of a graph into two equal size subsets that maximizes the number of edges with endpoints in both subsets. We obtain new improved approximation ratios for the max-bisection problem on the low degree k-regular graphs for 3 less than or equal to k less than or equal to 8, by deriving some improved transformations from a maximum cut intofrom a maximum bisection. In the case of three regular graphs we obtain an approximation ratio of 0.854, and in the case of four and five regular graphs, approximation ratios of 0.805, and 0.812, respectively.},
  author       = {Karpinski, M and Kowaluk, M and Lingas, Andrzej},
  issn         = {0169-2968},
  keyword      = {graph bisection,approximation algorithms,regular graphs},
  language     = {eng},
  number       = {3-4},
  pages        = {369--375},
  publisher    = {IOS Press},
  series       = {Fundamenta Informaticae},
  title        = {Approximation algorithms for MAX-BISECTION on low degree regular graphs},
  volume       = {62},
  year         = {2004},
}