| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 420679 | Discrete Applied Mathematics | 2009 | 12 Pages |
Abstract
In the Minimum Sum Edge Coloring problem we have to assign positive integers to the edges of a graph such that adjacent edges receive different integers and the sum of the assigned numbers is minimal. We show that the problem is (a) NP-hard for planar bipartite graphs with maximum degree 3, (b) NP-hard for 3-regular planar graphs, (c) NP-hard for partial 2-trees, and (d) APX-hard for bipartite graphs.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Dániel Marx,