Name
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(nk+c) steps where c 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. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1007/3-540-44683-4_27 | MFCS |
Keywords | Field | DocType |
sufficient condition,non parameterized vertex,subset c,number k,graph h,fixed preimages,hard cases,h-coloring problem,functional dependency | Discrete mathematics,Graph,NP-complete,Combinatorics,Parameterized complexity,Vertex (geometry),Graph colouring,Bipartite graph,Mathematics,Computational complexity theory | Conference |
Volume | ISSN | ISBN |
2136 | 0302-9743 | 3-540-42496-2 |
Citations | PageRank | References |
9 | 0.59 | 6 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Josep Díaz | 1 | 489 | 204.59 |
| Maria J. Serna | 2 | 473 | 70.53 |
| Dimitrios M. Thilikos | 3 | 1844 | 124.72 |