Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 2000 Copyright 2000 Universität Bonn, Institut für Informatik, Abt. V
8960

A Note on Approximating MAX-BISECTION on Regular Graphs
Uriel Feige, Marek Karpinski and Michael Langberg
[Download PostScript] [Download PDF]

We design a 0.795 approximation algorithm for the Max-Bisection problem restricted to regular graphs. In the case of three regular graphs our results imply an approximation ratio of 0.834.

Last Change: 11/05/14 at 10:17:17
 English
Universität Bonn -> Institut für Informatik -> Abteilung V