Name
Abstract | ||
|---|---|---|
The problem of counting all H-colorings of a graph G with n vertices is considered. While the problem is, in general, #P-complete, we give linear time algorithms that solve the main variants of this problem when the input graph G is a k-tree or, in the case where G is directed, when the underlying graph of G is a k-tree. Our algorithms remain polynomial even in the case where k=O(logn) or in the case where the size of H is O(n). Our results are easy to implement and imply the existence of polynomial time algorithms for a series of problems on partial k-trees such as core checking and chromatic polynomial computation. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1016/S0304-3975(02)00017-8 | Theor. Comput. Sci. |
Keywords | Field | DocType |
graph homomorphism,counting problems,treewidth | Wheel graph,Discrete mathematics,Combinatorics,Graph power,Tutte polynomial,Factor-critical graph,Chromatic polynomial,Windmill graph,Voltage graph,Mathematics,Complement graph | Journal |
Volume | Issue | ISSN |
281 | 1-2 | 0304-3975 |
Citations | PageRank | References |
9 | 0.67 | 28 |
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 |