Edge-Coloring Bipartite Graphs |
| |
Authors: | Ajai Kapoor Romeo Rizzi |
| |
Institution: | Dipartimento di Matematica Pura ed Applicata, Università di Padova, Via Belzoni 7, 35131, Padova, Italy |
| |
Abstract: | Given a bipartite graph G with n nodes, m edges, and maximum degree Δ, we find an edge-coloring for G using Δ colors in time T + O(m log Δ), where T is the time needed to find a perfect matching in a k-regular bipartite graph with O(m) edges and k ≤ Δ. Together with best known bounds for T this implies on
edge-coloring algorithm which improves on the
algorithm of Hopcroft and Cole. Our algorithm can also be used to find a (Δ + 2)-edge-coloring for G in time O(m log Δ). The previous best approximation algorithm with the same time bound needed Δ + log Δ colors. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|