|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'506'133
Articles rated: 2609
27 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Bounds and Fixed-Parameter Algorithms for Weighted Improper Coloring (Extended Version) | | Bjarki Ágúst Guðmundsson
; Tómas Ken Magnússon
; Björn Orri Sæmundsson
; | | Date: |
1 Sep 2015 | | Abstract: | We study the weighted improper coloring problem, a generalization of
defective coloring. We present some hardness results and in particular we show
that weighted improper coloring is not fixed-parameter tractable when
parameterized by pathwidth. We generalize bounds for defective coloring to
weighted improper coloring and give a bound for weighted improper coloring in
terms of the sum of edge weights. Finally we give fixed-parameter algorithms
for weighted improper coloring both when parameterized by treewidth and maximum
degree and when parameterized by treewidth and precision of edge weights. In
particular, we obtain a linear-time algorithm for weighted improper coloring of
interval graphs of bounded degree. | | Source: | arXiv, 1509.0099 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER