The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Approximation algorithms for MAX-BISECTION on low degree regular graphs

På svenska

Author

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.

Department/s

  • Computer Science

Publishing year

2004

Language

English

Pages

369-375

Publication/Series

Fundamenta Informaticae

Volume

62

Issue

3-4

Document type

Journal article

Publisher

IOS Press

Topic

  • Computer Science

Keywords

  • graph bisection
  • approximation algorithms
  • regular graphs

Status

Published

Project

  • VR 2002-4049

ISBN/ISSN/Other

  • ISSN: 0169-2968