Name
Abstract | ||
|---|---|---|
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 consider- able importance in both combinatorics and statistical physics. It contains several other polynomial invari- ants, such as the chromatic polynomial and flow poly- nomial 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 ex- perimental data comparing these heuristics against a range of others to demonstrate their effectiveness. |
Year | Venue | Keywords |
|---|---|---|
2010 | Chicago J. Theor. Comput. Sci. | edge-selection heuristics,various numerical invariants,dense graph,2-variable polynomial graph invariant,present experimental data,polynomial invariants,efficient algorithm to-date,flow polynomial,chromatic polynomial,tutte polynomial,potts model,spanning tree,statistical physics,partition function,partial evaluation |
Field | DocType | Volume |
Tutte 12-cage,Discrete mathematics,Combinatorics,Polynomial,Tutte polynomial,Bracket polynomial,Matrix polynomial,Chromatic polynomial,Mathematics,Graph coloring,Tutte matrix | Journal | 2010 |
Citations | PageRank | References |
3 | 0.52 | 5 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| David J. Pearce | 1 | 378 | 29.53 |
| Gary Haggard | 2 | 31 | 7.33 |
| Gordon Royle | 3 | 39 | 5.05 |