REPORTS > KEYWORD > REGULAR GRAPHS:
Reports tagged with Regular Graphs:
TR00-043
| 21st June 2000
Uriel Feige, Marek Karpinski, Michael Langberg
Uriel Feige, Marek Karpinski, Michael Langberg
A Note on Approximating MAX-BISECTION on Regular Graphs
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$.
TR00-051
| 14th July 2000
Marek Karpinski, Miroslaw Kowaluk, Andrzej Lingas
Marek Karpinski, Miroslaw Kowaluk, Andrzej Lingas
Approximation Algorithms for MAX-BISECTION on Low Degree Regular Graphs and Planar Graphs
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 ...
more >>>