Online Version - Last Updated - 20 Jan 2012 |
 |
| Home |
| |
| Procedures and Resources for Authors |
|
| Information and Resources for Volume Editors |
| |
| Orders and Subscriptions |
| |
| Published Articles |
|
| Upcoming Volumes |
| |
| Contact Us |
| |
| Useful External Links |
| |
| CRPIT Site Search |
Edge-Selection Heuristics for Computing Tutte Polynomials
Pearce, D., Haggard, G. and Royle, G.
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.
Cite as: Pearce, D., Haggard, G. and Royle, G. (2009). Edge-Selection Heuristics for Computing Tutte Polynomials. In Proc. Fifteenth Computing: The Australasian Theory Symposium (CATS 2009), Wellington, New Zealand. CRPIT, 94. Downey, R. and Manyem, P., Eds. ACS. 151-159.
(from crpit.com)
(local if available)
