Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR00-043 | 21st June 2000 00:00

A Note on Approximating MAX-BISECTION on Regular Graphs

RSS-Feed

Abstract:


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.



ISSN 1433-8092 | Imprint