CMU-CS-98-176Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-98-176
Ljubomir Perkovic' November 1998 Ph.D. Thesis
CMU-CS-98-176.ps
Keywords: Graph theory, edge coloring, design and analysis of
algorithms, combinatorial optimization, polyhedral combinatorics,
probabilistic analysis of algorithms, randomized algorithms
The required number of colors is called the chromatic index of the
graph. We consider the edge coloring problem in the framework of the
relationship between an integer program and its linear programming
relaxation. To do this we first formulate edge coloring as an integer
program and we define the fractional chromatic index to be the optimum
of its linear programming relaxation. For any graph of maximum degree
In this thesis we show that large classes of graphs satisfy this equality. More precisely, we show that if a graph is large enough, has large maximum degree and satisfies two technical conditions, then the equality holds. The constructive proof provides a randomized polynomial time algorithm for optimally coloring the edges of such graphs. We use a deterministic version of this algorithm to design the first algorithm that computes an optimal edge coloring of any graph in polynomial time, on average. 160 pages
| |

Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |