{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T01:47:52Z","timestamp":1725587272381},"publisher-location":"Berlin, Heidelberg","reference-count":44,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642220050"},{"type":"electronic","value":"9783642220067"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22006-7_45","type":"book-chapter","created":{"date-parts":[[2011,6,20]],"date-time":"2011-06-20T07:44:05Z","timestamp":1308555845000},"page":"533-544","source":"Crossref","is-referenced-by-count":1,"title":["Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width"],"prefix":"10.1007","author":[{"given":"Magnus","family":"Bordewich","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ross J.","family":"Kang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"45_CR1","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1002\/rsa.3240060409","volume":"6","author":"N. Alon","year":"1995","unstructured":"Alon, N., Frieze, A., Welsh, D.: Polynomial time randomized approximation schemes for Tutte-Gr\u00f6thendieck invariants: the dense case. Random Structures Algorithms\u00a06(4), 459\u2013478 (1995)","journal-title":"Random Structures Algorithms"},{"issue":"1-3","key":"45_CR2","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0012-365X(98)00113-7","volume":"190","author":"A. Andrzejak","year":"1998","unstructured":"Andrzejak, A.: An algorithm for the Tutte polynomials of graphs of bounded treewidth. Discrete Math.\u00a0190(1-3), 39\u201354 (1998)","journal-title":"Discrete Math."},{"issue":"4","key":"45_CR3","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1007\/s00493-004-0035-6","volume":"24","author":"R. Arratia","year":"2004","unstructured":"Arratia, R., Bollob\u00e1s, B., Sorkin, G.B.: A two-variable interlace polynomial. Combinatorica\u00a024(4), 567\u2013584 (2004)","journal-title":"Combinatorica"},{"issue":"3","key":"45_CR4","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/s00440-004-0369-4","volume":"131","author":"N. Berger","year":"2005","unstructured":"Berger, N., Kenyon, C., Mossel, E., Peres, Y.: Glauber dynamics on trees and hyperbolic graphs. Probab. Theory Related Fields\u00a0131(3), 311\u2013340 (2005)","journal-title":"Probab. Theory Related Fields"},{"issue":"1-4","key":"45_CR5","doi-asserted-by":"publisher","first-page":"42","DOI":"10.2307\/1967597","volume":"14","author":"G.D. Birkhoff","year":"1912","unstructured":"Birkhoff, G.D.: A determinant formula for the number of ways of coloring a map. Ann.\u00a0of Math.\u00a0(2)\u00a014(1-4), 42\u201346 (1912\/1913)","journal-title":"Ann.\u00a0of Math.\u00a0(2)"},{"key":"45_CR6","doi-asserted-by":"crossref","unstructured":"Bl\u00e4ser, M., Hoffmann, C.: Fast evaluation of interlace polynomials on graphs of bounded treewidth. To appear in Algorithmica, doi:10.1007\/s00453-010-9439-4","DOI":"10.1007\/s00453-010-9439-4"},{"key":"45_CR7","unstructured":"Bl\u00e4ser, M., Hoffmann, C.: On the complexity of the interlace polynomial. In: Albers, S., Weil, P. (eds.) 25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008), Dagstuhl, Germany. Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a01, pp. 97\u2013108. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik (2008)"},{"key":"45_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/11917496_1","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"H.L. Bodlaender","year":"2006","unstructured":"Bodlaender, H.L.: Treewidth: Characterizations, applications, and computations. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol.\u00a04271, pp. 1\u201314. Springer, Heidelberg (2006)"},{"issue":"1","key":"45_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1017\/S0963548303005844","volume":"13","author":"M. Bordewich","year":"2004","unstructured":"Bordewich, M.: Approximating the number of acyclic orientations for a class of sparse graphs. Combin. Probab. Comput.\u00a013(1), 1\u201316 (2004)","journal-title":"Combin. Probab. Comput."},{"key":"45_CR10","doi-asserted-by":"crossref","unstructured":"Courcelle, B.: A multivariate interlace polynomial and its computation for graphs of bounded clique-width. Electron. J. Combin.\u00a015(1): Research Paper 69, 36 (2008)","DOI":"10.37236\/793"},{"issue":"2","key":"45_CR11","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1214\/09-AAP627","volume":"20","author":"A. Dembo","year":"2010","unstructured":"Dembo, A., Montanari, A.: Ising models on locally tree-like graphs. Ann. Appl. Probab.\u00a020(2), 565\u2013592 (2010)","journal-title":"Ann. Appl. Probab."},{"issue":"1","key":"45_CR12","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1007\/s00220-009-0978-y","volume":"295","author":"J. Ding","year":"2010","unstructured":"Ding, J., Lubetzky, E., Peres, Y.: Mixing time of critical Ising model on trees is polynomial in the height. Comm. Math. Phys.\u00a0295(1), 161\u2013207 (2010)","journal-title":"Comm. Math. Phys."},{"key":"45_CR13","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/978-0-8176-4789-6_9","volume-title":"Structural Analysis of Complex Networks","author":"J.A. Ellis-Monaghan","year":"2011","unstructured":"Ellis-Monaghan, J.A., Merino, C.: Graph polynomials and their applications I: The Tutte polynomial. In: Dehmer, M. (ed.) Structural Analysis of Complex Networks, pp. 219\u2013255. Birkh\u00e4user, Boston (2011)"},{"key":"45_CR14","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/978-0-8176-4789-6_10","volume-title":"Structural Analysis of Complex Networks","author":"J.A. Ellis-Monaghan","year":"2011","unstructured":"Ellis-Monaghan, J.A., Merino, C.: Graph polynomials and their applications II: Interrelations and interpretations. In: Dehmer, M. (ed.) Structural Analysis of Complex Networks, pp. 257\u2013292. Birkh\u00e4user, Boston (2011)"},{"issue":"4","key":"45_CR15","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1016\/j.jda.2005.06.004","volume":"4","author":"F.V. Fomin","year":"2006","unstructured":"Fomin, F.V., Thilikos, D.M.: A 3-approximation for the pathwidth of Halin graphs. J. Discrete Algorithms\u00a04(4), 499\u2013510 (2006)","journal-title":"J. Discrete Algorithms"},{"key":"45_CR16","unstructured":"Ge, Q., \u0160tefankovi\u010d, D.: A graph polynomial for independent sets of bipartite graphs. CoRR, abs\/0911.4732 (2009)"},{"key":"45_CR17","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1063\/1.1703954","volume":"4","author":"R.J. Glauber","year":"1963","unstructured":"Glauber, R.J.: Time-dependent statistics of the Ising model. J. Mathematical Phys.\u00a04, 294\u2013307 (1963)","journal-title":"J. Mathematical Phys."},{"key":"45_CR18","unstructured":"Goldberg, L.A., Jerrum, M.: Personal communication (2010)"},{"key":"45_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1007\/978-3-642-14165-2_34","volume-title":"Automata, Languages and Programming","author":"L.A. Goldberg","year":"2010","unstructured":"Goldberg, L.A., Jerrum, M.: Approximating the partition function of the ferromagnetic potts model. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol.\u00a06198, pp. 396\u2013407. Springer, Heidelberg (2010)"},{"issue":"4","key":"45_CR20","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1002\/rsa.20303","volume":"36","author":"L.A. Goldberg","year":"2010","unstructured":"Goldberg, L.A., Jerrum, M., Karpinski, M.: The mixing time of Glauber dynamics for coloring regular trees. Random Structures Algorithms\u00a036(4), 464\u2013476 (2010)","journal-title":"Random Structures Algorithms"},{"key":"45_CR21","series-title":"Grundlehren der Mathematischen Wissenschaften (Fundamental Principles of Mathematical Sciences)","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-32891-9","volume-title":"The random-cluster model","author":"G. Grimmett","year":"2006","unstructured":"Grimmett, G.: The random-cluster model. Grundlehren der Mathematischen Wissenschaften (Fundamental Principles of Mathematical Sciences), vol.\u00a0333. Springer, Berlin (2006)"},{"issue":"1","key":"45_CR22","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1093\/biomet\/57.1.97","volume":"57","author":"W.K. Hastings","year":"1970","unstructured":"Hastings, W.K.: Monte Carlo sampling methods using Markov chains and their applications. Biometrika\u00a057(1), 97\u2013109 (1970)","journal-title":"Biometrika"},{"issue":"3","key":"45_CR23","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1093\/comjnl\/bxm052","volume":"51","author":"P. Hlin\u011bn\u00fd","year":"2008","unstructured":"Hlin\u011bn\u00fd, P., Oum, S.-i., Seese, D., Gottlob, G.: Width Parameters Beyond Tree-width and their Applications. The Computer Journal\u00a051(3), 326\u2013362 (2008)","journal-title":"The Computer Journal"},{"key":"45_CR24","first-page":"253","volume":"31","author":"E. Ising","year":"1925","unstructured":"Ising, E.: Beitrag zur theorie des ferromagnetismus. Zeitschrift f\u00fcr Physik A Hadrons and Nuclei\u00a031, 253\u2013258 (1925), doi:10.1007\/BF02980577","journal-title":"Zeitschrift f\u00fcr Physik A Hadrons and Nuclei"},{"issue":"1","key":"45_CR25","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1017\/S0305004100068936","volume":"108","author":"F. Jaeger","year":"1990","unstructured":"Jaeger, F., Vertigan, D.L., Welsh, D.J.A.: On the computational complexity of the Jones and Tutte polynomials. Math.\u00a0Proc.\u00a0Cambridge Philos.\u00a0Soc.\u00a0108(1), 35\u201353 (1990)","journal-title":"Math.\u00a0Proc.\u00a0Cambridge Philos.\u00a0Soc."},{"key":"45_CR26","series-title":"Lectures in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-8005-3","volume-title":"Counting, sampling and integrating: algorithms and complexity","author":"M. Jerrum","year":"2003","unstructured":"Jerrum, M.: Counting, sampling and integrating: algorithms and complexity, ETH Z\u00fcrich. Lectures in Mathematics. Birkh\u00e4user, Basel (2003)"},{"issue":"5","key":"45_CR27","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1137\/0222066","volume":"22","author":"M. Jerrum","year":"1993","unstructured":"Jerrum, M., Sinclair, A.: Polynomial-time approximation algorithms for the Ising model. SIAM J. Comput.\u00a022(5), 1087\u20131116 (1993)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"45_CR28","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1090\/S0273-0979-1985-15304-2","volume":"12","author":"V.F.R. Jones","year":"1985","unstructured":"Jones, V.F.R.: A polynomial invariant for knots via von Neumann algebras. Bull. Amer. Math. Soc (N.S.)\u00a012(1), 103\u2013111 (1985)","journal-title":"Bull. Amer. Math. Soc. (N.S.)"},{"issue":"3","key":"45_CR29","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1137\/S0036144501387141","volume":"43","author":"D.R. Karger","year":"2001","unstructured":"Karger, D.R.: A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem. SIAM Rev.\u00a043(3), 499\u2013522 (2001)","journal-title":"SIAM Rev."},{"issue":"6","key":"45_CR30","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/0020-0190(92)90234-M","volume":"42","author":"N.G. Kinnersley","year":"1992","unstructured":"Kinnersley, N.G.: The vertex separation number of a graph equals its path-width. Inform.\u00a0Process.\u00a0Lett.\u00a042(6), 345\u2013350 (1992)","journal-title":"Inform.\u00a0Process.\u00a0Lett."},{"issue":"3-4","key":"45_CR31","doi-asserted-by":"publisher","first-page":"542","DOI":"10.1007\/s00224-007-9022-9","volume":"43","author":"J.A. Makowsky","year":"2008","unstructured":"Makowsky, J.A.: From a zoo to a zoology: towards a general theory of graph polynomials. Theory Comput. Syst.\u00a043(3-4), 542\u2013562 (2008)","journal-title":"Theory Comput. Syst."},{"issue":"1-2","key":"45_CR32","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1016\/S0196-8858(02)00530-4","volume":"30","author":"J.A. Makowsky","year":"2003","unstructured":"Makowsky, J.A., Mari\u00f1o, J.P.: Farrell polynomials on graphs of bounded tree width. Adv.\u00a0in Appl.\u00a0Math.\u00a030(1-2), 160\u2013176 (2003), Formal power series and algebraic combinatorics, Scottsdale, AZ (2001)","journal-title":"Adv.\u00a0in Appl.\u00a0Math."},{"issue":"2","key":"45_CR33","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1002\/rsa.20132","volume":"31","author":"F. Martinelli","year":"2007","unstructured":"Martinelli, F., Sinclair, A., Weitz, D.: Fast mixing for independent sets, colorings, and other models on trees. Random Structures Algorithms\u00a031(2), 134\u2013172 (2007)","journal-title":"Random Structures Algorithms"},{"issue":"6","key":"45_CR34","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1063\/1.1699114","volume":"21","author":"N. Metropolis","year":"1953","unstructured":"Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H., Teller, E.: Equation of state calculations by fast computing machines. The Journal of Chemical Physics\u00a021(6), 1087\u20131092 (1953)","journal-title":"The Journal of Chemical Physics"},{"issue":"3","key":"45_CR35","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1017\/S0963548398003551","volume":"7","author":"S.D. Noble","year":"1998","unstructured":"Noble, S.D.: Evaluating the Tutte polynomial for graphs of bounded tree-width. Combin. Probab. Comput.\u00a07(3), 307\u2013321 (1998)","journal-title":"Combin. Probab. Comput."},{"key":"45_CR36","doi-asserted-by":"crossref","unstructured":"Noble, S.D.: Evaluating a weighted graph polynomial for graphs of bounded tree-width. Electron. J. Combin. 16(1): research Paper 64, 14 (2009)","DOI":"10.37236\/153"},{"issue":"3","key":"45_CR37","doi-asserted-by":"publisher","first-page":"1057","DOI":"10.5802\/aif.1706","volume":"49","author":"S.D. Noble","year":"1999","unstructured":"Noble, S.D., Welsh, D.J.A.: A weighted graph polynomial from chromatic invariants of knots. Ann. Inst. Fourier\u00a049(3), 1057\u20131087 (1999), Symposium \u00e0 la M\u00e9moire de Fran\u00e7ois Jaeger, Grenoble (1998)","journal-title":"Ann. Inst. Fourier"},{"key":"45_CR38","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1017\/S0305004100027419","volume":"48","author":"R.B. Potts","year":"1952","unstructured":"Potts, R.B.: Some generalized order-disorder transformations. Proc.\u00a0Cambridge Philos.\u00a0Soc.\u00a048, 106\u2013109 (1952)","journal-title":"Proc.\u00a0Cambridge Philos.\u00a0Soc."},{"issue":"2","key":"45_CR39","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1109\/MCSE.2006.30","volume":"8","author":"D. Randall","year":"2006","unstructured":"Randall, D.: Rapidly mixing Markov chains with applications in computer science and physics. Computing in Science Engineering\u00a08(2), 30\u201341 (2006)","journal-title":"Computing in Science Engineering"},{"key":"45_CR40","series-title":"London Math. Soc. Lecture Note Ser.","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1017\/CBO9780511734885.009","volume-title":"Surveys in Combinatorics 2005","author":"A.D. Sokal","year":"2005","unstructured":"Sokal, A.D.: The multivariate Tutte polynomial (alias Potts model) for graphs and matroids. In: Surveys in Combinatorics 2005. London Math. Soc. Lecture Note Ser., vol.\u00a0327, pp. 173\u2013226. Cambridge Univ. Press, Cambridge (2005)"},{"key":"45_CR41","first-page":"1646","volume-title":"SODA","author":"P. Tetali","year":"2010","unstructured":"Tetali, P., Vera, J.C., Vigoda, E., Yang, L.: Phase transition for the mixing time of the Glauber dynamics for coloring regular trees. In: Charikar, M. (ed.) SODA, pp. 1646\u20131656. SIAM, Philadelphia (2010)"},{"key":"45_CR42","unstructured":"Thomas, R.: Tree-decompositions of graphs (1996), Lecture notes http:\/\/www.math.gatech.edu\/~thomas\/tree.ps"},{"key":"45_CR43","doi-asserted-by":"publisher","first-page":"80","DOI":"10.4153\/CJM-1954-010-9","volume":"6","author":"W.T. Tutte","year":"1954","unstructured":"Tutte, W.T.: A contribution to the theory of chromatic polynomials. Canadian J. Math.\u00a06, 80\u201391 (1954)","journal-title":"Canadian J. Math."},{"key":"45_CR44","series-title":"London Mathematical Society Lecture Note Series","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511752506","volume-title":"Complexity: knots, colourings and counting","author":"D.J.A. Welsh","year":"1993","unstructured":"Welsh, D.J.A.: Complexity: knots, colourings and counting. London Mathematical Society Lecture Note Series, vol.\u00a0186. Cambridge University Press, Cambridge (1993)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22006-7_45","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,7]],"date-time":"2024-04-07T20:30:12Z","timestamp":1712521812000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22006-7_45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642220050","9783642220067"],"references-count":44,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22006-7_45","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}