Další formáty:
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Ý a Marc NOY. Computing the Tutte Polynomial on Graphs of Bounded Clique-Width. \textit{SIAM Journal on Discrete Mathematics}. Philadelphia: SIAM, 2006, roč.~20, č.~4, s.~932-946. ISSN~0895-4801.
|