Ehemalige Mitarbeiter

Prof. Dr. Martin Lotz

Kontakt
Mathematics Institute
Zeeman Building
University of Warwick
Coventry CV4 7AL
United Kingdom

Persönliche Homepage
http://homepages.warwick.ac.uk/staff/Martin.Lotz/

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.