research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Article
Entered by:
TitleApproximate constrained bipartite edge coloring
Bibtex cite IDRACTI-RU1-2004-49
Journal Discrete Applied Mathematics
Year published 2004
Month September
Volume 143
Number 1-3
Pages 54-61
ISSN 0166-218X
DOI 10.1016/j.dam.2003.12.006
Keywords Edge coloring; Multicommodity Bows; Randomized rounding
We study the following Constrained Bipartite Edge Coloring problem: We are given a bipartite graph G=(U,V,E) of maximum degree I with n vertices, in which some of the edges have been legally colored with c colors. We wish to complete the coloring of the edges of G minimizing the total number of colors used. The problem has been proved to be NP-hard even for bipartite graphs of maximum degree three. Two special cases of the problem have been previously considered and tight upper and ower bounds on the optimal number of colors were proved. The upper bounds led to 3/2-approximation algorithms for both problems. In this paper we present a randomized (1.37+o(1))-approximation algorithm for the general problem in the case where maxl,c = ù(ln n). Our techniques are motivated by recent works on the Circular Arc Coloring problem and are essentially different and simpler than the existing ones.
Caragiannis, Ioannis
Ferreira, A.
Kaklamanis, Christos
Perrenes, S.
Persianno, P.
Rivano, H.
getPDF.pdf (main file)
Publication ID579