CJTCS Special Issue: CATS 2009
Selected papers from
2009 Computing: The Australasian Theory Symposium
held in Wellington, New Zealand January 20-23 2009.
Guest Editors: Rod Downey, Victoria University of Wellington, NZ
Prabhu Manyem, Shanghai University, PRC.
Published by the Department of Computer Science, The University of Chicago.
Edge-Selection Heuristics for Computing Tutte Polynomials
David J. Pearce
Computer Science Group,
Victoria University of Wellington
PO Box 600, Wellington 6140
School of Mathematics and Statistics,
University of Western Australia.
June 22, 2010
The Tutte polynomial of a graph, also known as the partition
function of the q-state Potts model, is a 2-variable polynomial
graph invariant of considerable importance in both combinatorics and
statistical physics. It contains several other polynomial
invariants, such as the chromatic polynomial and flow polynomial as
partial evaluations, and various numerical invariants, such as the
number of spanning trees, as complete evaluations. We have
developed the most efficient algorithm to-date for computing the
Tutte polynomial of a graph. An important component of the
algorithm affecting efficiency is the choice of edge to work on at
each stage in the computation. In this paper, we present and
discuss two edge-selection heuristics which (respectively) give good
performance on sparse and dense graphs. We also present
experimental data comparing these heuristics against a range of
others to demonstrate their effectiveness.
- The article: PDF (225,200 bytes)
- Source materials: ZIP (124,872 bytes)
- Self citation in
BIBTeX (205 bytes)
- Original version (pre-June 2010): PDF (178,116 bytes)
© 2010 David J. Pearce, David J. Pearce and Gordon Royle
Licensed under a Creative Commons Attribution License
Special Issue, CATS 2009, Article 2