Approximation algorithms for MAX-BISECTION on low degree regular graphs
Författare
Summary, in English
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.
Avdelning/ar
- Computer Science
Publiceringsår
2004
Språk
Engelska
Sidor
369-375
Publikation/Tidskrift/Serie
Fundamenta Informaticae
Volym
62
Issue
3-4
Dokumenttyp
Artikel i tidskrift
Förlag
IOS Press
Ämne
- Computer Science
Nyckelord
- graph bisection
- approximation algorithms
- regular graphs
Status
Published
Projekt
- VR 2002-4049
ISBN/ISSN/Övrigt
- ISSN: 0169-2968