Fetching the paper…
Reading the bibliography…
The deletion--contraction algorithm is perhaps the most popular method for computing a host of fundamental graph invariants such as the chromatic, flow, and reliability polynomials in graph theory, the Jones polynomial of an alternating link in knot theory, and the partition functions of the models of Ising, Potts, and Fortuin--Kasteleyn in statistical physics.
R. B. Potts, Some generalized order-disorder transformations , Proceedings of the Cambridge Philosophical Society 48
1952
Earlier work this paper cites.
P. W. Kasteleyn, The statistics of dimers on a lattice: I. The number of dimer arrangements on a quadratic lattice , Physica 27
1961
Earlier work this paper cites.
C. M. Fortuin, P. W. Kasteleyn, On the random-cluster model. I. Introduction and relation to other models , Physica 57
1972
Earlier work this paper cites.
E. L. Lawler, A note on the complexity of the chromatic number problem , Inf. Process. Lett. 5
1976
Earlier work this paper cites.
S. Kohn, A. Gottlieb, M. Kohn, A generating function approach to the traveling salesman problem , Proceedings of the 1977 Annual Conference (ACM’77), Association for Computing Machinery, 1977, pp. 294–300
1977
Earlier work this paper cites.
J. G. Oxley, D. J. A. Welsh, The Tutte polynomial and percolation , Graph Theory and Related Topics (J. A. Bondy and U. S. R. Murty, Eds.), Academic Press, 1979, pp. 329–339
1979
Earlier work this paper cites.
L. G. Valiant, The complexity of enumeration and reliability problems , SIAM J. Comput. 8
1979
Earlier work this paper cites.
J. A. Buzacott, A recursive algorithm for finding reliability measures related to the connection of nodes in a graph , Networks 10
1980
Earlier work this paper cites.
R. M. Karp, Dynamic programming meets the principle of inclusion and exclusion , Oper. Res. Lett. 1
1982
Earlier work this paper cites.
H. S. Wilf, Algorithms and Complexity , Prentice–Hall, 1986
1986
Earlier work this paper cites.
M. H. G. Anthony, Computing chromatic polynomials , Ars Combinatoria 29
1990
Earlier work this paper cites.
F. Jaeger, D. L. Vertigan, D. J. A. Welsh, On the computational complexity of the Jones and Tutte polynomials , Math. Proc. Cambridge Philos. Soc. 108
1990
Earlier work this paper cites.
N. Biggs, Algebraic Graph Theory , 2nd ed., Cambridge University Press, 1993
1993
Earlier work this paper cites.
D. E. Knuth, The Stanford GraphBase: A Platform for Combinatorial Computing , Association for Computing Machinery, 1993
1993
Earlier work this paper cites.
D. J. A. Welsh, Complexity: Knots, Colourings and Counting , London Mathematical Society Lecture Note Series 186, Cambridge University Press, 1993
1993
Earlier work this paper cites.
J. D. Annan, The complexities of the coefficients of the Tutte polynomial , Discrete Appl. Math. 57
1995
Cited alongside, same era.
F. R. K. Chung, R. L. Graham, On the cover polynomial of a digraph , J. Combin. Theory Ser. B 65
1995
Cited alongside, same era.
S. Kapoor, H. Ramesh, Algorithms for enumerating all spanning trees of undirected and weighted graphs , SIAM J. Comput. 24
1995
Cited alongside, same era.
K. Sekine, H. Imai, S. Tani, Computing the Tutte polynomial of a graph of moderate size , Algorithms and Computation, 6th International Symposium (ISAAC ’95), Cairns, Australia, December 4–6, 1995, Lecture Notes in Computer Science 1004, Springer, 1995, pp. 224–233
1995
Cited alongside, same era.
A. Andrzejak, An algorithm for the Tutte polynomials of graphs of bounded treewidth , Discrete Math. 190
1998
Cited alongside, same era.
W. T. Tutte, Graph-polynomials , Adv. Appl. Math. 32
2004
Later among the works it cites.
A. D. Sokal, The multivariate Tutte polynomial (alias Potts model) for graphs and matroids , Surveys in Combinatorics, 2005, London Mathematical Society Lecture Note Series 327, Cambridge University Press, 2005, pp. 173–226
2005
Later among the works it cites.
R. Williams, A new algorithm for optimal constraint satisfaction and its implications , Theoret. Comput. Sci. 348
2005
Later among the works it cites.
O. Giménez, P. Hliněný, M. Noy, Computing the Tutte polynomial on graphs of bounded clique-width , SIAM J. Discrete Math. 20
2006
Later among the works it cites.
P. Hliněný, The Tutte polynomial for matroids of bounded branch-width , Combin. Probab. Comput. 15
2006
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
B. Bollobás, Modern Graph Theory , Graduate Texts in Mathematics 184, Springer, 1998
1998
Cited alongside, same era.
S. D. Noble, Evaluating the Tutte polynomial for graphs of bounded tree-width , Combin. Probab. Comput. 7
1998
Cited alongside, same era.
F. Chung, S.-T. Yau, Coverings, heat kernels, and spanning trees , Electron. J. Combinatorics 6
1999
Cited alongside, same era.
W. Kook, V. Reiner, D. Stanton, A convolution formula for the Tutte polynomial , J. Combin. Theory Ser. B 76
1999
Cited alongside, same era.
D. J. A. Welsh, The Tutte polynomial , Random Structures Algorithms 15
1999
Cited alongside, same era.
H. Imai, Computing the invariant polynomials of graphs, networks, and matroids , IEICE T. Inf. Syst. E93–D
2000
Cited alongside, same era.
D. J. A. Welsh, C. Merino, The Potts model and the Tutte polynomial , J. Math. Phys. 41
2000
Cited alongside, same era.
M. Koivisto, Optimal 2-constraint satisfaction via sum-product algorithms , Inform. Process. Lett. 98
2006
Later among the works it cites.
A. Björklund, T. Husfeldt, Exact algorithms for exact satisfiability and number of perfect matchings , Algorithmica, 2007, doi:10.1007/s00453-007-9149-8
2007
Closest in time.
A. Björklund, T. Husfeldt, P. Kaski, M. Koivisto, Fourier meets Möbius: fast subset convolution
2007
Closest in time.
M. Bläser, H. Dell, Complexity of the cover polynomial , Proceedings of the 34th International Colloquium on Automata, Languages and Programming (Wroclaw, Poland, July 9-13, 2007), Lecture Notes in Computer Science 4596, 2007, pp. 801-812
2007
Closest in time.
F. V. Fomin, S. Gaspers, S. Saurabh, Improved exact algorithms for counting 3- and 4-colorings , Computing and Combinatorics, 13th Annual International Conference (COCOON), Banff, Canada, July 16–19, 2007, Lecture Notes in Computer Science 4598, Springer, 2007, pp. 65–74
2007
Closest in time.
H. Gebauer, Y. Okamoto, Fast exponential-time algorithms for the forest counting in graph classes , Theory of Computing 2007, Proceedings of the 13th Computing: The Australasian Theory Symposium (CATS 2007), Ballarat, Victoria, Jan 30–Feb 2, 2007, Conferences in Research and Practice in Information Technology 65, Australian Computer Society, 2007, pp. 63–69
2007
Closest in time.
2007
Closest in time.
L. A. Goldberg, M. Jerrum, Inapproximability of the Tutte polynomial , Proceedings of the 39th Annual ACM Symposium on Theory of Computing (San Diego, CA, June 11–13, 2007), Association for Computing Machinery, 2007, pp. 459–468
2007
Closest in time.
A. Björklund, T. Husfeldt, P. Kaski, M. Koivisto, The Travelling Salesman Problem in bounded degree graphs , Proceedings of the 35th International Colloquium on Automata, Languages and Programming (Reykjavik, Iceland, July 6–13, 2008), to appear
2008
Closest in time.
P. Traxler, The Time Complexity of Constraint Satisfaction , Proceedings of the 3rd International Workshop on Exact and Parameterized Computation (Victoria (BC), Canada, May 14–16, 2008), to appear
2008
Closest in time.