Other formats:
BibTeX
LaTeX
RIS
@inproceedings{579781,
author = {Gimenez, Omer and Hliněný, Petr and Noy, Marc},
address = {Berlin},
booktitle = {WG 2005},
keywords = {Tutte polynomial; cographs; clique-width; subexponential algorithm; U polynomial},
language = {eng},
location = {Berlin},
isbn = {978-3-540-31000-6},
pages = {59-68},
publisher = {Springer Verlag},
title = {Computing the Tutte Polynomial on Graphs of Bounded Clique-Width (extended abstract)},
url = {http://www.informatik.uni-trier.de/~ley/db/conf/wg/},
year = {2005}
}
TY - JOUR
ID - 579781
AU - Gimenez, Omer - Hliněný, Petr - Noy, Marc
PY - 2005
TI - Computing the Tutte Polynomial on Graphs of Bounded Clique-Width (extended abstract)
PB - Springer Verlag
CY - Berlin
SN - 9783540310006
KW - Tutte polynomial
KW - cographs
KW - clique-width
KW - subexponential algorithm
KW - U polynomial
UR - http://www.informatik.uni-trier.de/~ley/db/conf/wg/
N2 - The Tutte polynomial is a notoriously hard graph invariant, and efficient algorithms for it are known only for a few special graph classes, like for those of bounded tree-width. The notion of clique-width extends the definition of cograhs (graphs without induced P4), and it is a more general notion than that of tree-width. We show a subexponential algorithm (running in time expO(n2/3) ) for computing the Tutte polynomial on cographs. The algorithm can be extended to a subexponential algorithm computing the Tutte polynomial on on all graphs of bounded clique-width. In fact, our algorithm computes the more general U-polynomial.
ER -
GIMENEZ, Omer, Petr HLINĚNÝ and Marc NOY. Computing the Tutte Polynomial on Graphs of Bounded Clique-Width (extended abstract). D. Kratsch (Ed.). In \textit{WG 2005}. Berlin: Springer Verlag, 2005, p.~59-68. ISBN~978-3-540-31000-6.
|
