Given a multigraph G=(V,E), the Edge Coloring Problem (ECP) calls for the minimum number X 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 ((2k+1)X+(2k-2))/2k (rounded up) colors. For k&lt;= 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 ((2k+1)X+(2k-3))/2k (rounded up) 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; Caprara, Alberto. - ELETTRONICO. - (1998), pp. 1-6.

### Improving a Family of Approximation Algorithms to Edge Color Multigraphs

#### Abstract

Given a multigraph G=(V,E), the Edge Coloring Problem (ECP) calls for the minimum number X 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 ((2k+1)X+(2k-2))/2k (rounded up) colors. For k<= 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 ((2k+1)X+(2k-3))/2k (rounded up) 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.
##### Scheda breve Scheda completa Scheda completa (DC)
1998
Trento, Italia
Università degli Studi di Trento. DEPARTMENT OF INFORMATION AND COMMUNICATION TECHNOLOGY
Improving a Family of Approximation Algorithms to Edge Color Multigraphs / Rizzi, Romeo; Caprara, Alberto. - ELETTRONICO. - (1998), pp. 1-6.
Rizzi, Romeo; Caprara, Alberto
File in questo prodotto:
File
49.pdf

accesso aperto

Tipologia: Versione editoriale (Publisher’s layout)
Dimensione 192.17 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11572/358449`