Další formáty:
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Ý a 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, s.~59-68. ISBN~978-3-540-31000-6.
|