Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.jda.2006.03.020 | Journal of Discrete Algorithms |
Keywords | Field | DocType |
distance-edge-coloring,algorithm,bounded integer,partial k-trees,planar graphs,distance-edge-coloring problem,polynomial-time exact algorithm,planar graph,2-approximation algorithm,graph g,partial k-tree,different color,partial k -trees,approximation algorithm,graph g.,edge coloring,polynomial time | Discrete mathematics,Edge coloring,Combinatorics,Comparability graph,Line graph,Fractional coloring,Algorithm,Graph minor,1-planar graph,Planar graph,Mathematics,Graph coloring | Journal |
Volume | Issue | ISSN |
5 | 2 | Journal of Discrete Algorithms |
ISBN | Citations | PageRank |
3-540-28061-8 | 7 | 0.59 |
References | Authors | |
17 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Takehiro Ito | 1 | 260 | 40.71 |
| Akira Kato | 2 | 7 | 0.59 |
| Xiao Zhou | 3 | 325 | 43.69 |
| Takao Nishizeki | 4 | 1771 | 267.08 |