Premium
The Tutte polynomial
Author(s) -
Welsh Dominic
Publication year - 1999
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199910/12)15:3/4<210::aid-rsa2>3.0.co;2-r
Subject(s) - struct , lattice (music) , random graph , tutte polynomial , polynomial , discrete mathematics , mathematics , combinatorics , computer science , physics , graph , mathematical analysis , line graph , voltage graph , acoustics , programming language
This is a close approximation to the content of my lecture. After a brief survey of well known properties, I present some new interpretations relating to random graphs, lattice point enumeration, and chip firing games. I then examine complexity issues and concentrate in particular, on the existence of randomized approximation schemes. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 15, 210–228, 1999