Given a multigraph G=(V,E), the Edge Coloring Problem (ECP) calls for the minimum number $\chi$ of colors needed to color the edges in E so that all edges incident with a common node are assigned different colors. The best known polynomial time approximation algorithms for ECP belong to a same family, which is likely to contain, for each positive integer k, an algorithm which uses at most $\lc((2k+1)\chi+(2k-2))/2k\rc$ colors. For $k\leq 5$ the existence of the corresponding algorithm was shown, whereas for larger values of k the question is open. We show that, for any k such that the corresponding algorithm exists, it is possible to improve the algorithm so as to use at most $\lc((2k+1)\chi+(2k-3))/2k\rc$ colors. It is easily shown that the $(2k-3)/2k$ term cannot be reduced further, unless P=NP. We also discuss how our result can be used to extend the set of cases in which well-known conjectures on ECP are valid.

Improving a Family of Approximation Algorithms to Edge Color Multigraphs

RIZZI, ROMEO
1998-01-01

Abstract

Given a multigraph G=(V,E), the Edge Coloring Problem (ECP) calls for the minimum number $\chi$ of colors needed to color the edges in E so that all edges incident with a common node are assigned different colors. The best known polynomial time approximation algorithms for ECP belong to a same family, which is likely to contain, for each positive integer k, an algorithm which uses at most $\lc((2k+1)\chi+(2k-2))/2k\rc$ colors. For $k\leq 5$ the existence of the corresponding algorithm was shown, whereas for larger values of k the question is open. We show that, for any k such that the corresponding algorithm exists, it is possible to improve the algorithm so as to use at most $\lc((2k+1)\chi+(2k-3))/2k\rc$ colors. It is easily shown that the $(2k-3)/2k$ term cannot be reduced further, unless P=NP. We also discuss how our result can be used to extend the set of cases in which well-known conjectures on ECP are valid.
1998
edge coloring; approximation algorithm; edge coloring multigraphs
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/409594
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 12
social impact