Almost linear time computation of the chromatic polynomial of a graph of bounded tree-width

Martin Furer

doi:10.1007/978-3-642-12200-2_6

Almost linear time computation of the chromatic polynomial of a graph of bounded tree-width

Martin Furer

Eberly College of Science

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

Abstract

An O(n log² n) algorithm is presented to compute all coefficients of the chromatic polynomial of an n vertex graph of bounded tree-width. Previously, it has been known how to evaluate the chromatic polynomial for such graphs in linear time, implying a computation of all coefficients of the chromatic polynomial in quadratic time.

Original language	English (US)
Title of host publication	LATIN 2010
Subtitle of host publication	Theoretical Informatics - 9th Latin American Symposium, Proceedings
Pages	49-59
Number of pages	11
DOIs	https://doi.org/10.1007/978-3-642-12200-2_6
State	Published - 2010
Event	9th Latin American Theoretical Informatics Symposium, LATIN 2010 - Oaxaca, Mexico Duration: Apr 19 2010 → Apr 23 2010

Publication series

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

Other

Other	9th Latin American Theoretical Informatics Symposium, LATIN 2010
Country/Territory	Mexico
City	Oaxaca
Period	4/19/10 → 4/23/10

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-12200-2_6

Cite this

Furer, M. (2010). Almost linear time computation of the chromatic polynomial of a graph of bounded tree-width. In LATIN 2010: Theoretical Informatics - 9th Latin American Symposium, Proceedings (pp. 49-59). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6034 LNCS). https://doi.org/10.1007/978-3-642-12200-2_6

@inproceedings{88d9db5d872e457b8898f7ee7f47cb54,

title = "Almost linear time computation of the chromatic polynomial of a graph of bounded tree-width",

abstract = "An O(n log2 n) algorithm is presented to compute all coefficients of the chromatic polynomial of an n vertex graph of bounded tree-width. Previously, it has been known how to evaluate the chromatic polynomial for such graphs in linear time, implying a computation of all coefficients of the chromatic polynomial in quadratic time.",

author = "Martin Furer",

year = "2010",

doi = "10.1007/978-3-642-12200-2_6",

language = "English (US)",

isbn = "3642121993",

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

pages = "49--59",

booktitle = "LATIN 2010",

note = "9th Latin American Theoretical Informatics Symposium, LATIN 2010 ; Conference date: 19-04-2010 Through 23-04-2010",

}

Furer, M 2010, Almost linear time computation of the chromatic polynomial of a graph of bounded tree-width. in LATIN 2010: Theoretical Informatics - 9th Latin American Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6034 LNCS, pp. 49-59, 9th Latin American Theoretical Informatics Symposium, LATIN 2010, Oaxaca, Mexico, 4/19/10. https://doi.org/10.1007/978-3-642-12200-2_6

Almost linear time computation of the chromatic polynomial of a graph of bounded tree-width. / Furer, Martin.
LATIN 2010: Theoretical Informatics - 9th Latin American Symposium, Proceedings. 2010. p. 49-59 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6034 LNCS).

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

TY - GEN

T1 - Almost linear time computation of the chromatic polynomial of a graph of bounded tree-width

AU - Furer, Martin

PY - 2010

Y1 - 2010

N2 - An O(n log2 n) algorithm is presented to compute all coefficients of the chromatic polynomial of an n vertex graph of bounded tree-width. Previously, it has been known how to evaluate the chromatic polynomial for such graphs in linear time, implying a computation of all coefficients of the chromatic polynomial in quadratic time.

AB - An O(n log2 n) algorithm is presented to compute all coefficients of the chromatic polynomial of an n vertex graph of bounded tree-width. Previously, it has been known how to evaluate the chromatic polynomial for such graphs in linear time, implying a computation of all coefficients of the chromatic polynomial in quadratic time.

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

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

U2 - 10.1007/978-3-642-12200-2_6

DO - 10.1007/978-3-642-12200-2_6

M3 - Conference contribution

AN - SCOPUS:77953483938

SN - 3642121993

SN - 9783642121999

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

SP - 49

EP - 59

BT - LATIN 2010

T2 - 9th Latin American Theoretical Informatics Symposium, LATIN 2010

Y2 - 19 April 2010 through 23 April 2010

ER -

Furer M. Almost linear time computation of the chromatic polynomial of a graph of bounded tree-width. In LATIN 2010: Theoretical Informatics - 9th Latin American Symposium, Proceedings. 2010. p. 49-59. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-12200-2_6

Almost linear time computation of the chromatic polynomial of a graph of bounded tree-width

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this