{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T13:40:01Z","timestamp":1780062001149,"version":"3.54.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2010,9,1]],"date-time":"2010-09-01T00:00:00Z","timestamp":1283299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["737730"],"award-info":[{"award-number":["737730"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2010,9]]},"abstract":"<jats:p>\n            The Tutte polynomial of a graph, also known as the partition function of the\n            <jats:italic>q<\/jats:italic>\n            -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. However despite its ubiquity, there are no widely available effective computational tools able to compute the Tutte polynomial of a general graph of reasonable size. In this article we describe the implementation of a program that exploits isomorphisms in the computation tree to extend the range of graphs for which it is feasible to compute their Tutte polynomials, and we demonstrate the utility of the program by finding counterexamples to a conjecture of Welsh on the location of the real flow roots of a graph.\n          <\/jats:p>","DOI":"10.1145\/1824801.1824802","type":"journal-article","created":{"date-parts":[[2010,9,28]],"date-time":"2010-09-28T17:41:41Z","timestamp":1285695701000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Computing Tutte Polynomials"],"prefix":"10.1145","volume":"37","author":[{"given":"Gary","family":"Haggard","sequence":"first","affiliation":[{"name":"Bucknell University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David J.","family":"Pearce","sequence":"additional","affiliation":[{"name":"Victoria University of Wellington, NZ"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gordon","family":"Royle","sequence":"additional","affiliation":[{"name":"University of Western, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2010,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.40"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"}}Bj\u00f6rklund A. Husfeldt T. Kaski P. and Koivistor M. 2008b. Computing the Tutte Polynomial in vertex-exponential time. Tech. rep. arxiv.org\/PS_cache\/arxiv\/pdf\/0711\/0711.2585v4.pdf.  }} Bj\u00f6rklund A. Husfeldt T. Kaski P. and Koivistor M. 2008b. Computing the Tutte Polynomial in vertex-exponential time. Tech. rep. arxiv.org\/PS_cache\/arxiv\/pdf\/0711\/0711.2585v4.pdf.","DOI":"10.1109\/FOCS.2008.40"},{"key":"e_1_2_1_3_1","volume-title":"No. 184","author":"Bollob\u00e1s B.","unstructured":"}} Bollob\u00e1s , B. 1998. Modern Graph Theory. Graduate Texts in Mathematics , No. 184 . Springer , New York . }}Bollob\u00e1s, B. 1998. Modern Graph Theory. Graduate Texts in Mathematics, No. 184. Springer, New York."},{"key":"e_1_2_1_4_1","volume-title":"Matroid Applications. Encyclopedia Mathematical Applications","volume":"40","author":"Brylawski T.","unstructured":"}} Brylawski , T. and Oxley , J . 1992. The Tutte polynomial and its applications . In Matroid Applications. Encyclopedia Mathematical Applications , vol. 40 . Cambridge University Press, Cambridge, UK, 123--225. }}Brylawski, T. and Oxley, J. 1992. The Tutte polynomial and its applications. In Matroid Applications. Encyclopedia Mathematical Applications, vol. 40. Cambridge University Press, Cambridge, UK, 123--225."},{"key":"e_1_2_1_5_1","first-page":"61","article-title":"The random planar graph","volume":"113","author":"Denise A.","year":"1996","unstructured":"}} Denise , A. , Vasconcellos , M. , and Welsh , D. J. A. 1996 . The random planar graph . Congressus Numerantium 113 , 61 -- 79 . }}Denise, A., Vasconcellos, M., and Welsh, D. J. A. 1996. The random planar graph. Congressus Numerantium 113, 61--79.","journal-title":"Congressus Numerantium"},{"key":"e_1_2_1_6_1","volume-title":"I: The Tutte Polynomial. In Structural Analysis of Complex Networks","author":"Ellis-Monaghan J.","year":"2009","unstructured":"}} Ellis-Monaghan , J. and Merino , C . 2009 a. Graph polynomials and their applications I: The Tutte Polynomial. In Structural Analysis of Complex Networks . http:\/\/arxiv.org\/abs\/0803.3079. }}Ellis-Monaghan, J. and Merino, C. 2009a. Graph polynomials and their applications I: The Tutte Polynomial. In Structural Analysis of Complex Networks. http:\/\/arxiv.org\/abs\/0803.3079."},{"key":"e_1_2_1_7_1","volume-title":"II: Interrelations and interpretations. In Structural Analysis of Complex Networks","author":"Ellis-Monaghan J.","year":"2009","unstructured":"}} Ellis-Monaghan , J. and Merino , C . 2009 b. Graph polynomials and their applications II: Interrelations and interpretations. In Structural Analysis of Complex Networks . http:\/\/arxiv.org\/abs\/0806.4699. }}Ellis-Monaghan, J. and Merino, C. 2009b. Graph polynomials and their applications II: Interrelations and interpretations. In Structural Analysis of Complex Networks. http:\/\/arxiv.org\/abs\/0806.4699."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 8th International Symposium on Graph Drawing (GD). Springer-Verlag, 77--90","author":"Gutwenger C.","unstructured":"}} Gutwenger , C. and Mutzel , P . 2001. A linear time implementation of SPQR-trees . In Proceedings of the 8th International Symposium on Graph Drawing (GD). Springer-Verlag, 77--90 . }}Gutwenger, C. and Mutzel, P. 2001. A linear time implementation of SPQR-trees. In Proceedings of the 8th International Symposium on Graph Drawing (GD). Springer-Verlag, 77--90."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00343-4"},{"key":"e_1_2_1_10_1","first-page":"35","article-title":"Chromatic polynomials of large graphs II. Isomorphism abstract data type for small graphs","volume":"3","author":"Haggard G.","year":"1993","unstructured":"}} Haggard , G. and Read , R. 1993 . Chromatic polynomials of large graphs II. Isomorphism abstract data type for small graphs . J. Math. Comput. 3 , 35 -- 43 . }}Haggard, G. and Read, R. 1993. Chromatic polynomials of large graphs II. Isomorphism abstract data type for small graphs. J. Math. Comput. 3, 35--43.","journal-title":"J. Math. Comput."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1965-0179110-1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202012"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100068936"},{"key":"e_1_2_1_14_1","volume-title":"Department of Computer Science","author":"McKay B.","unstructured":"}} McKay , B. 1990. Nauty users guide (version 1.5). Tech. rep ., Department of Computer Science , Australian National University . }}McKay, B. 1990. Nauty users guide (version 1.5). Tech. rep., Department of Computer Science, Australian National University."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the Computing: The Australasian Theory Symposium (CATS). 153--162","author":"Pearce D. J.","unstructured":"}} Pearce , D. J. , Haggard , G. , and Royle , G . 2009. Edge-selection heuristics for computing Tutte Polynomials . In Proceedings of the Computing: The Australasian Theory Symposium (CATS). 153--162 . }}Pearce, D. J., Haggard, G., and Royle, G. 2009. Edge-selection heuristics for computing Tutte Polynomials. In Proceedings of the Computing: The Australasian Theory Symposium (CATS). 153--162."},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"}}Pemmaraju S. and Skiena S. 2003. Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge University Press Cambridge UK.   }} Pemmaraju S. and Skiena S. 2003. Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica . Cambridge University Press Cambridge UK.","DOI":"10.1017\/CBO9781139164849"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195434"},{"key":"e_1_2_1_18_1","volume-title":"An improved method for computing chromatic polynomials of sparse graphs. Tech. rep. CORR 87-20","author":"Read R.","unstructured":"}} Read , R. 1987. An improved method for computing chromatic polynomials of sparse graphs. Tech. rep. CORR 87-20 , University of Waterloo . }}Read, R. 1987. An improved method for computing chromatic polynomials of sparse graphs. Tech. rep. CORR 87-20, University of Waterloo."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70508-9"},{"key":"e_1_2_1_20_1","volume-title":"Computing the Tutte polynomial of sparse graphs. Tech. rep. CORR 88-35","author":"Royle G. F.","unstructured":"}} Royle , G. F. 1988. Computing the Tutte polynomial of sparse graphs. Tech. rep. CORR 88-35 , University of Waterloo . }}Royle, G. F. 1988. Computing the Tutte polynomial of sparse graphs. Tech. rep. CORR 88-35, University of Waterloo."},{"key":"e_1_2_1_21_1","volume-title":"Lecture Notes in Computer Science","volume":"1004","author":"Sekine K.","unstructured":"}} Sekine , K. , Imai , H. , and Tani , S . 1995. Computing the Tutte polynomial of a graph of moderate size . Lecture Notes in Computer Science , vol. 1004 . Springer, 224--233. }}Sekine, K., Imai, H., and Tani, S. 1995. Computing the Tutte polynomial of a graph of moderate size. Lecture Notes in Computer Science, vol. 1004. Springer, 224--233."},{"key":"e_1_2_1_22_1","volume-title":"Surveys in Combinatorics","author":"Sokal A. D.","unstructured":"}} Sokal , A. D. 2005. The multivariate Tutte polynomial (alias Potts model) for graphs and matroids . In Surveys in Combinatorics . London Mathematics Society. Lecture Note Series, vol. 327 . Cambridge University Press , Cambridge, UK, 173--226. }}Sokal, A. D. 2005. The multivariate Tutte polynomial (alias Potts model) for graphs and matroids. In Surveys in Combinatorics. London Mathematics Society. Lecture Note Series, vol. 327. Cambridge University Press, Cambridge, UK, 173--226."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1954-010-9"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758773"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1824801.1824802","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1824801.1824802","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:39:54Z","timestamp":1750246794000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1824801.1824802"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,9]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,9]]}},"alternative-id":["10.1145\/1824801.1824802"],"URL":"https:\/\/doi.org\/10.1145\/1824801.1824802","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,9]]},"assertion":[{"value":"2009-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}