{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:32:37Z","timestamp":1771036357050,"version":"3.50.1"},"publisher-location":"Cham","reference-count":24,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030581497","type":"print"},{"value":"9783030581503","type":"electronic"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-58150-3_54","type":"book-chapter","created":{"date-parts":[[2020,8,27]],"date-time":"2020-08-27T01:02:42Z","timestamp":1598490162000},"page":"664-676","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Mixing of Markov Chains for Independent Sets on Chordal Graphs with Bounded Separators"],"prefix":"10.1007","author":[{"given":"Ivona","family":"Bez\u00e1kov\u00e1","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wenbo","family":"Sun","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,8,27]]},"reference":[{"key":"54_CR1","doi-asserted-by":"crossref","unstructured":"Anari, N., Liu, K., Gharan, S.O.: Spectral independence in high-dimensional expanders and applications to the hardcore model. In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC). ACM (2020)","DOI":"10.1109\/FOCS46700.2020.00125"},{"issue":"4","key":"54_CR2","doi-asserted-by":"publisher","first-page":"P4.19","DOI":"10.37236\/4195","volume":"21","author":"M Bordewich","year":"2014","unstructured":"Bordewich, M., Kang, R.J.: Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width. Electr. J. Comb. 21(4), P4.19 (2014)","journal-title":"Electr. J. Comb."},{"issue":"3","key":"54_CR3","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0012-365X(74)90002-8","volume":"9","author":"P Buneman","year":"1974","unstructured":"Buneman, P., et al.: A characterisation of rigid circuit graphs. Discrete Math. 9(3), 205\u2013212 (1974)","journal-title":"Discrete Math."},{"issue":"1","key":"54_CR4","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1006\/jagm.1999.1071","volume":"35","author":"M Dyer","year":"2000","unstructured":"Dyer, M., Greenhill, C.: On Markov chains for independent sets. J. Algorithms 35(1), 17\u201349 (2000)","journal-title":"J. Algorithms"},{"key":"54_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1007\/978-3-030-30786-8_23","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"M Dyer","year":"2019","unstructured":"Dyer, M., Greenhill, C., M\u00fcller, H.: Counting independent sets in graphs with bounded bipartite pathwidth. In: Sau, I., Thilikos, D.M. (eds.) WG 2019. LNCS, vol. 11789, pp. 298\u2013310. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-30786-8_23"},{"issue":"5","key":"54_CR6","doi-asserted-by":"publisher","first-page":"1527","DOI":"10.1137\/S0097539701383844","volume":"31","author":"ME Dyer","year":"2002","unstructured":"Dyer, M.E., Frieze, A.M., Jerrum, M.: On counting independent sets in sparse graphs. SIAM J. Comput. 31(5), 1527\u20131541 (2002)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"54_CR7","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1137\/17M1127144","volume":"48","author":"C Efthymiou","year":"2019","unstructured":"Efthymiou, C., Hayes, T.P., \u0160tefankovi\u010d, D., Vigoda, E., Yin, Y.: Convergence of MCMC and loopy BP in the tree uniqueness region for the hard-core model. SIAM J. Comput. 48(2), 581\u2013643 (2019)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"54_CR8","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1002\/rsa.20479","volume":"45","author":"A Galanis","year":"2014","unstructured":"Galanis, A., Ge, Q., \u0160tefankovi\u010d, D., Vigoda, E., Yang, L.: Improved inapproximability results for counting independent sets in the hard-core model. Random Struct. Algorithms 45(1), 78\u2013110 (2014)","journal-title":"Random Struct. Algorithms"},{"issue":"4","key":"54_CR9","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1017\/S0963548315000401","volume":"25","author":"A Galanis","year":"2016","unstructured":"Galanis, A., \u0160tefankovi\u010d, D., Vigoda, E.: Inapproximability of the partition function for the antiferromagnetic ising and hard-core models. Comb. Probab. Comput. 25(4), 500\u2013559 (2016)","journal-title":"Comb. Probab. Comput."},{"issue":"1","key":"54_CR10","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"F Gavril","year":"1974","unstructured":"Gavril, F.: The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Comb. Theory Ser. B 16(1), 47\u201356 (1974)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"5","key":"54_CR11","doi-asserted-by":"publisher","first-page":"695","DOI":"10.1017\/S0963548312000296","volume":"21","author":"Q Ge","year":"2012","unstructured":"Ge, Q., \u0160tefankovi\u010d, D.: A graph polynomial for independent sets of bipartite graphs. Comb. Probab. Comput. 21(5), 695\u2013714 (2012)","journal-title":"Comb. Probab. Comput."},{"key":"54_CR12","doi-asserted-by":"crossref","unstructured":"Jerrum, M.: Counting, Sampling and Integrating: Algorithms and Complexity. Birh\u00e4user (2003)","DOI":"10.1007\/978-3-0348-8005-3"},{"issue":"6","key":"54_CR13","doi-asserted-by":"publisher","first-page":"1149","DOI":"10.1137\/0218077","volume":"18","author":"M Jerrum","year":"1989","unstructured":"Jerrum, M., Sinclair, A.: Approximating the permanent. SIAM J. Comput. 18(6), 1149\u20131178 (1989)","journal-title":"SIAM J. Comput."},{"key":"54_CR14","volume-title":"Probabilistic Graphical Models: Principles and Techniques","author":"D Koller","year":"2009","unstructured":"Koller, D., Friedman, N.: Probabilistic Graphical Models: Principles and Techniques. MIT press, Cambridge (2009)"},{"issue":"3\u20134","key":"54_CR15","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<229::AID-RSA3>3.0.CO;2-X","volume":"15","author":"M Luby","year":"1999","unstructured":"Luby, M., Vigoda, E.: Fast convergence of the Glauber dynamics for sampling independent sets. Random Struct. Algorithms 15(3\u20134), 229\u2013241 (1999)","journal-title":"Random Struct. Algorithms"},{"key":"54_CR16","unstructured":"Matthews, J.: Markov chains for sampling matchings. Ph.D. Thesis, University of Edinburgh (2008)"},{"key":"54_CR17","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/s00440-007-0131-9","volume":"143","author":"E Mossel","year":"2009","unstructured":"Mossel, E., Weitz, D., Wormald, N.: On the hardness of sampling independent sets beyond the tree threshold. Probab. Theory Rel. Fields 143, 401\u2013439 (2009)","journal-title":"Probab. Theory Rel. Fields"},{"key":"54_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/11604686_38","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"Y Okamoto","year":"2005","unstructured":"Okamoto, Y., Uno, T., Uehara, R.: Linear-time counting algorithms for independent sets in chordal Graphs. In: Kratsch, D. (ed.) WG 2005. LNCS, vol. 3787, pp. 433\u2013444. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11604686_38"},{"issue":"4","key":"54_CR19","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1017\/S0963548300000390","volume":"1","author":"A Sinclair","year":"1992","unstructured":"Sinclair, A.: Improved bounds for mixing rates of Markov chains and multicommodity flow. Comb. Prob. Comput. 1(4), 351\u2013370 (1992)","journal-title":"Comb. Prob. Comput."},{"key":"54_CR20","doi-asserted-by":"crossref","unstructured":"Sly, A.: Computational transition at the uniqueness threshold. In: 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pp. 287\u2013296. IEEE (2010)","DOI":"10.1109\/FOCS.2010.34"},{"issue":"6","key":"54_CR21","doi-asserted-by":"publisher","first-page":"2383","DOI":"10.1214\/13-AOP888","volume":"42","author":"A Sly","year":"2014","unstructured":"Sly, A., Sun, N.: Counting in two-spin models on $$d$$-regular graphs. Ann. Probab. 42(6), 2383\u20132416 (2014)","journal-title":"Ann. Probab."},{"issue":"4","key":"54_CR22","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1561\/2400000006","volume":"1","author":"L Vandenberghe","year":"2015","unstructured":"Vandenberghe, L., Andersen, M.S., et al.: Chordal graphs and semidefinite optimization. Found. Trends \u00ae Optim. 1(4), 241\u2013433 (2015)","journal-title":"Found. Trends \u00ae Optim."},{"issue":"1","key":"54_CR23","doi-asserted-by":"publisher","first-page":"R8","DOI":"10.37236\/1552","volume":"8","author":"E Vigoda","year":"2001","unstructured":"Vigoda, E.: A note on the Glauber dynamics for sampling independent sets. Electr. J. Comb. 8(1), R8 (2001)","journal-title":"Electr. J. Comb."},{"key":"54_CR24","doi-asserted-by":"crossref","unstructured":"Weitz, D.: Counting independent sets up to the tree threshold. In: Proceedings of the 38th Annual ACM symposium on Theory of Computing (STOC), pp. 140\u2013149 (2006)","DOI":"10.1145\/1132516.1132538"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-58150-3_54","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,24]],"date-time":"2021-04-24T05:44:16Z","timestamp":1619243056000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-58150-3_54"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030581497","9783030581503"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-58150-3_54","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"27 August 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Atlanta, GA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 August 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31 August 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/cocoon-conference.org\/2020\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"126","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"54","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"43% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2.7","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"10.2","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference was held virtually due to the COVID-19 pandemic.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}