Counting H-colorings of partial k-trees

Josep Dìaz; Maria Serna; Dimitrios M. Thilikos

doi:10.1007/3-540-44679-6_33

Counting H-colorings of partial k-trees

Josep Dìaz, Maria Serna, Dimitrios M. Thilikos

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

The problem of counting all H-colorings of a graph G of 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(log n) 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.

Original language	English (US)
Title of host publication	Computing and Combinatorics - 7th Annual International Conference, COCOON 2001, Proceedings
Editors	Jie Wang
Publisher	Springer Verlag
Pages	298-307
Number of pages	10
ISBN (Print)	9783540424949
DOIs	https://doi.org/10.1007/3-540-44679-6_33
State	Published - 2001
Event	7th Annual International Conference on Computing and Combinatorics, COCOON 2001 - Guilin, China Duration: Aug 20 2001 → Aug 23 2001

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2108
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	7th Annual International Conference on Computing and Combinatorics, COCOON 2001
Country/Territory	China
City	Guilin
Period	8/20/01 → 8/23/01

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-44679-6_33

Cite this

Dìaz, J., Serna, M., & Thilikos, D. M. (2001). Counting H-colorings of partial k-trees. In J. Wang (Ed.), Computing and Combinatorics - 7th Annual International Conference, COCOON 2001, Proceedings (pp. 298-307). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2108). Springer Verlag. https://doi.org/10.1007/3-540-44679-6_33

Counting H-colorings of partial k-trees. / Dìaz, Josep; Serna, Maria; Thilikos, Dimitrios M.
Computing and Combinatorics - 7th Annual International Conference, COCOON 2001, Proceedings. ed. / Jie Wang. Springer Verlag, 2001. p. 298-307 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2108).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Dìaz, J, Serna, M & Thilikos, DM 2001, Counting H-colorings of partial k-trees. in J Wang (ed.), Computing and Combinatorics - 7th Annual International Conference, COCOON 2001, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2108, Springer Verlag, pp. 298-307, 7th Annual International Conference on Computing and Combinatorics, COCOON 2001, Guilin, China, 8/20/01. https://doi.org/10.1007/3-540-44679-6_33

Dìaz J, Serna M, Thilikos DM. Counting H-colorings of partial k-trees. In Wang J, editor, Computing and Combinatorics - 7th Annual International Conference, COCOON 2001, Proceedings. Springer Verlag. 2001. p. 298-307. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-44679-6_33

Dìaz, Josep ; Serna, Maria ; Thilikos, Dimitrios M. / Counting H-colorings of partial k-trees. Computing and Combinatorics - 7th Annual International Conference, COCOON 2001, Proceedings. editor / Jie Wang. Springer Verlag, 2001. pp. 298-307 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{09547e31c3794fd48c655c3536c41245,

title = "Counting H-colorings of partial k-trees",

abstract = "The problem of counting all H-colorings of a graph G of 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(log n) 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.",

author = "Josep D{\`i}az and Maria Serna and Thilikos, {Dimitrios M.}",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2001.; 7th Annual International Conference on Computing and Combinatorics, COCOON 2001 ; Conference date: 20-08-2001 Through 23-08-2001",

year = "2001",

doi = "10.1007/3-540-44679-6_33",

language = "English (US)",

isbn = "9783540424949",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "298--307",

editor = "Jie Wang",

booktitle = "Computing and Combinatorics - 7th Annual International Conference, COCOON 2001, Proceedings",

}

TY - GEN

T1 - Counting H-colorings of partial k-trees

AU - Dìaz, Josep

AU - Serna, Maria

AU - Thilikos, Dimitrios M.

PY - 2001

Y1 - 2001

N2 - The problem of counting all H-colorings of a graph G of 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(log n) 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.

AB - The problem of counting all H-colorings of a graph G of 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(log n) 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.

UR - http://www.scopus.com/inward/record.url?scp=84944145309&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84944145309&partnerID=8YFLogxK

U2 - 10.1007/3-540-44679-6_33

DO - 10.1007/3-540-44679-6_33

M3 - Conference contribution

AN - SCOPUS:84944145309

SN - 9783540424949

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 298

EP - 307

BT - Computing and Combinatorics - 7th Annual International Conference, COCOON 2001, Proceedings

A2 - Wang, Jie

PB - Springer Verlag

T2 - 7th Annual International Conference on Computing and Combinatorics, COCOON 2001

Y2 - 20 August 2001 through 23 August 2001

ER -

Counting H-colorings of partial k-trees

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this