Name
Abstract | ||
|---|---|---|
We investigate the parameterized complexity of the following edge coloring problem motivated by the problem of channel assignment in wireless networks. For an integer q >= 2 and a graph G, the goal is to find a coloring of the edges of G with the maximum number of colors such that every vertex of the graph sees at most q colors. This problem is NP-hard for q >= 2, and has been well-studied from the point of view of approximation. Our main focus is the case when q = 2, which is already theoretically intricate and practically relevant. We show fixed-parameter tractable algorithms for both the standard and the dual parameter, and for the latter problem, the result is based on a linear vertex kernel. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/978-3-642-40313-2_44 | Lecture Notes in Computer Science |
DocType | Volume | ISSN |
Journal | 8087 | 0302-9743 |
Citations | PageRank | References |
0 | 0.34 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Prachi Goyal | 1 | 9 | 1.52 |
| Vikram Kamat | 2 | 24 | 4.72 |
| Neeldhara Misra | 3 | 341 | 31.42 |