Idioma:

Bounds and Fixed-Parameter Algorithms for Weighted Improper Coloring

Gudmundsson, Bjarki Agust ; Magnusson, Tomas Ken ; Saemundsson, Bjorn Orri

Electronic notes in theoretical computer science, 2016-04, Vol.322, p.181-195

Texto completo disponível

Citações Citado por

Título:
Bounds and Fixed-Parameter Algorithms for Weighted Improper Coloring
Autor: Gudmundsson, Bjarki Agust ; Magnusson, Tomas Ken ; Saemundsson, Bjorn Orri
Assuntos: coloring bounds ; defective coloring ; fixed-parameter algorithms ; graph coloring ; improper coloring ; weighted improper coloring
É parte de: Electronic notes in theoretical computer science, 2016-04, Vol.322, p.181-195
Descrição: 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.
Editor: Elsevier B.V
Idioma: Inglês

Voltar para lista de resultados

Anterior Resultado 6 Avançar Ir para próxima página