TU Berlin

Fachgebiet Algorithmische AlgebraPublications

Inhalt des Dokuments

zur Navigation

Search for Publication

Suche nach Publikationen

All Publications

On the algebraic complexity of some families of coloured Tutte polynomials
Zitatschlüssel LM-On-The-Algebraic-Complexity-Of-Some-Families-Of-Coloured-Tutte-Polynomials
Autor Martin Lotz and Johann Andreas Makowsky
Seiten 327-349
Jahr 2004
Journal Advances in Applied Mathematics
Jahrgang 32
Nummer 1-2
Zusammenfassung We investigate the coloured Tutte polynomial in Valiant's algebraic framework of NP-completeness. Generalising the well known relationship between the Tutte polynomial and the partition function from the Ising model, we establish a reduction from the permanent to the coloured Tutte polynomial, thus showing that its evaluation is a VNP-complete problem.
Link zur Publikation Link zur Originalpublikation Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe