Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Regular Graphs:
TR00-043 | 21st June 2000
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$.

more >>>

TR00-051 | 14th July 2000
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 >>>

TR19-040 | 19th February 2019
Sanjana Kolisetty, Linh Le, Ilya Volkovich, Mihalis Yannakakis

The Complexity of Finding {$S$}-factors in Regular Graphs

A graph $G$ has an \emph{$S$-factor} if there exists a spanning subgraph $F$ of $G$ such that for all $v \in V: \deg_F(v) \in S$.
The simplest example of such factor is a $1$-factor, which corresponds to a perfect matching in a graph. In this paper we study the computational ... more >>>

ISSN 1433-8092 | Imprint