Given a bipartite graph G with n nodes, m edges and maximum degree D, we find an edge coloring for G using D colors in time T + O(m log D), where T is the time needed to find a perfect matching in a k-regular bipartite graph with O(m) edges and k <= D. Together with best known bounds for T, this implies an O(m log D + (m/D) log (m/D) log^2 D) edge-coloring algorithm which improves on the O(m log D + (m/D) log (m/D) log^3 D) algorithm of Hopcroft and Cole. Our algorithm can also be used to find a (D+2)-edge-coloring for G in time O(m log D). The previous best approximation algorithm with the same time bound needed D + log D colors.

Edge­Coloring Bipartite Graphs / Kapoor, Ajai; Rizzi, Romeo. - ELETTRONICO. - (1999), pp. 1-6.

Edge­Coloring Bipartite Graphs

Rizzi, Romeo
1999-01-01

Abstract

Given a bipartite graph G with n nodes, m edges and maximum degree D, we find an edge coloring for G using D colors in time T + O(m log D), where T is the time needed to find a perfect matching in a k-regular bipartite graph with O(m) edges and k <= D. Together with best known bounds for T, this implies an O(m log D + (m/D) log (m/D) log^2 D) edge-coloring algorithm which improves on the O(m log D + (m/D) log (m/D) log^3 D) algorithm of Hopcroft and Cole. Our algorithm can also be used to find a (D+2)-edge-coloring for G in time O(m log D). The previous best approximation algorithm with the same time bound needed D + log D colors.
1999
Trento, Italia
Università degli Studi di Trento. DEPARTMENT OF INFORMATION AND COMMUNICATION TECHNOLOGY
Edge­Coloring Bipartite Graphs / Kapoor, Ajai; Rizzi, Romeo. - ELETTRONICO. - (1999), pp. 1-6.
Kapoor, Ajai; Rizzi, Romeo
File in questo prodotto:
File Dimensione Formato  
40.pdf

accesso aperto

Tipologia: Versione editoriale (Publisher’s layout)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 186.8 kB
Formato Adobe PDF
186.8 kB Adobe PDF Visualizza/Apri

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/11572/358461
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact