For a bounded integer ℓ, we wish to color all edges of a graph G so that any two edges within distance ℓ have different colors. Such a coloring is called a distance-edge-coloring or an ℓ-edge-coloring of G. The distance-edge-coloring problem is to compute the minimum number of colors required for a distance-edge-coloring of a given graph G. A partial k-tree is a graph with tree-width bounded by a fixed constant k. We first present a polynomial-time exact algorithm to solve the problem for partial k-trees, and then give a polynomial-time 2-approximation algorithm for planar graphs.
|Number of pages||10|
|Journal||Lecture Notes in Computer Science|
|Publication status||Published - 2005|
|Event||11th Annual International Conference on Computing and Combinatorics, COCOON 2005 - Kunming, China|
Duration: 2005 Aug 16 → 2005 Aug 29