Other formats:
BibTeX
LaTeX
RIS
@article{637507,
author = {Gimenez, Omer and Hliněný, Petr and Noy, Marc},
article_location = {Philadelphia},
article_number = {4},
keywords = {Tutte polynomial; cographs; clique-width; subexponential algorithm; U polynomial},
language = {eng},
issn = {0895-4801},
journal = {SIAM Journal on Discrete Mathematics},
title = {Computing the Tutte Polynomial on Graphs of Bounded Clique-Width},
url = {http://dx.doi.org/10.1137/050645208},
volume = {20},
year = {2006}
}
TY - JOUR
ID - 637507
AU - Gimenez, Omer - Hliněný, Petr - Noy, Marc
PY - 2006
TI - Computing the Tutte Polynomial on Graphs of Bounded Clique-Width
JF - SIAM Journal on Discrete Mathematics
VL - 20
IS - 4
SP - 932-946
EP - 932-946
PB - SIAM
SN - 08954801
KW - Tutte polynomial
KW - cographs
KW - clique-width
KW - subexponential algorithm
KW - U polynomial
UR - http://dx.doi.org/10.1137/050645208
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, and extend it 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. \textit{SIAM Journal on Discrete Mathematics}. Philadelphia: SIAM, 2006, vol.~20, No~4, p.~932-946. ISSN~0895-4801.
|
