Chicago Journal of Theoretical Computer Science

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.

Article 2010-6

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
New Zealand.,
Gary Haggard
Bucknell University,
Gordon Royle
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.

DOI: 10.4086/cjtcs.2010.006
© 2010 David J. Pearce, David J. Pearce and Gordon Royle
Creative Commons License Licensed under a Creative Commons Attribution License

[] Special Issue, CATS 2009, Article 2 [] Article 4

[back] Special Issue [back] Published articles
[CJCTS home]