ANALYSIS OF APPROXIMATE ALGORITHMS FOR EDGE-COLORING BIPARTITE GRAPHS

Authors
JAIN R WERTH J
Citation
R. Jain et J. Werth, ANALYSIS OF APPROXIMATE ALGORITHMS FOR EDGE-COLORING BIPARTITE GRAPHS, Information processing letters, 54(3), 1995, pp. 163-168
Citations number
10
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
54
Issue
3
Year of publication
1995
Pages
163 - 168
Database
ISI
SICI code
0020-0190(1995)54:3<163:AOAAFE>2.0.ZU;2-J
Abstract
The problem of edge-coloring a bipartite graph is to color the edges s o that adjacent edges receive different colors. An optimal algorithm u ses the minimum number of colors to color the edges. We consider sever al approximation algorithms for edge-coloring bipartite graphs and sho w tight bounds on the number of colors they use in the worst case. We also present results on the constrained edge-coloring problem where ea ch color may be used to color at most k edges.