Título:
|
(H,C,K)-colorings: fast, easy, and hard cases
|
Autor/a:
|
Díaz Cort, Josep; Serna Iglesias, María José; Thilikos Touloupas, Dimitrios
|
Otros autores:
|
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació |
Abstract:
|
We define a variant of the H-coloring problem by fixing the number
of preimages of a subset C of the vertices of H, thus allowing
parameterization. We provide sufficient conditions to guarantee that
the problem can be solved in O(kn+f(k,H)) steps where f is a
function depending only on the number k of fixed preimages and the
graph H, and in O(n^{k+alpha}) steps where alpha is a constant
independent of k. Finally, we prove that whenever the non
parameterized vertices induce in G a graph that is bipartite and
loopless the problem is NP-complete. |
Materia(s):
|
-Àrees temàtiques de la UPC::Informàtica -Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica -H-coloring |
Derechos:
|
|
Tipo de documento:
|
Artículo - Versión publicada Informe |
Compartir:
|
|