{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T15:37:36Z","timestamp":1787499456717,"version":"build-2736575974"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030307851","type":"print"},{"value":"9783030307868","type":"electronic"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","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":[[2019]]},"DOI":"10.1007\/978-3-030-30786-8_23","type":"book-chapter","created":{"date-parts":[[2019,9,11]],"date-time":"2019-09-11T17:22:57Z","timestamp":1568222577000},"page":"298-310","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Counting Independent Sets in Graphs with Bounded Bipartite Pathwidth"],"prefix":"10.1007","author":[{"given":"Martin","family":"Dyer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Catherine","family":"Greenhill","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Haiko","family":"M\u00fcller","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,9,12]]},"reference":[{"key":"23_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0166-218X(02)00290-1","volume":"135","author":"VE Alekseev","year":"2004","unstructured":"Alekseev, V.E.: Polynomial algorithm for finding the largest independent sets in graphs without forks. Discrete Appl. Math. 135, 3\u201316 (2004)","journal-title":"Discrete Appl. Math."},{"key":"23_CR2","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/978-3-319-44479-6_7","volume-title":"A Journey Through Discrete Mathematics","author":"A Barvinok","year":"2017","unstructured":"Barvinok, A.: Computing the partition function of a polynomial on the Boolean cube. In: Loebl, M., Ne\u0161et\u0159il, J., Thomas, R. (eds.) A Journey Through Discrete Mathematics, pp. 135\u2013164. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-44479-6_7"},{"key":"23_CR3","doi-asserted-by":"crossref","unstructured":"Bayati, M., Gamarnik, D., Katz, D., Nair, C., Tetali, P.: Simple deterministic approximation algorithms for counting matchings. In: Proceedings of the STOC, pp. 122\u2013127 (2007)","DOI":"10.1145\/1250790.1250809"},{"key":"23_CR4","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/S0021-9800(70)80019-9","volume":"9","author":"L Beineke","year":"1970","unstructured":"Beineke, L.: Characterizations of derived graphs. J. Comb. Theory 9, 129\u2013135 (1970)","journal-title":"J. Comb. Theory"},{"key":"23_CR5","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender, H.L.: A linear time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25, 1305\u20131317 (1996)","journal-title":"SIAM J. Comput."},{"key":"23_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"HL Bodlander","year":"1998","unstructured":"Bodlander, H.L.: A partial $$k$$ -arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209, 1\u201345 (1998)","journal-title":"Theor. Comput. Sci."},{"key":"23_CR7","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1016\/j.jctb.2006.06.001","volume":"97","author":"M Chudnovsky","year":"2007","unstructured":"Chudnovsky, M., Seymour, P.: The roots of the independence polynomial of a clawfree graph. J. Comb. Theory ( Ser. B) 97, 350\u2013357 (2007)","journal-title":"J. Comb. Theory ( Ser. B)"},{"key":"23_CR8","doi-asserted-by":"publisher","first-page":"696","DOI":"10.1214\/aoap\/1177005359","volume":"3","author":"P Diaconis","year":"1993","unstructured":"Diaconis, P., Saloff-Coste, L.: Comparison theorems for reversible Markov chains. Ann. Appl. Probab. 3, 696\u2013730 (1993)","journal-title":"Ann. Appl. Probab."},{"key":"23_CR9","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1214\/aoap\/1177005980","volume":"1","author":"P Diaconis","year":"1991","unstructured":"Diaconis, P., Stroock, D.: Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Probab. 1, 36\u201361 (1991)","journal-title":"Ann. Appl. Probab."},{"key":"23_CR10","series-title":"Graduate Texts in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53622-3","volume-title":"Graph Theory","author":"R Diestel","year":"2017","unstructured":"Diestel, R.: Graph Theory. Graduate Texts in Mathematics, vol. 173. Springer, Heidelberg (2017). https:\/\/doi.org\/10.1007\/978-3-662-53622-3"},{"key":"23_CR11","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1007\/s00453-003-1073-y","volume":"38","author":"M Dyer","year":"2003","unstructured":"Dyer, M., Goldberg, L.A., Greenhill, C., Jerrum, M.: On the relative complexity of approximate counting problems. Algorithmica 38, 471\u2013500 (2003)","journal-title":"Algorithmica"},{"key":"23_CR12","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, 17\u201349 (2000)","journal-title":"J. Algorithms"},{"key":"23_CR13","doi-asserted-by":"crossref","unstructured":"Dyer, M., Greenhill, C., M\u00fcller, H.: Counting independent sets in graphs with bounded bipartite pathwidth. Preprint: arXiv:1812.03195 (2018)","DOI":"10.1007\/978-3-030-30786-8_23"},{"key":"23_CR14","doi-asserted-by":"crossref","unstructured":"Efthymiou, C., Hayes, T., Stefankovic, D., Vigoda, E., Yin, Y.: Convergence of MCMC and loopy BP in the tree uniqueness region for the hard-core model. In: Proceedings of the FOCS 2016, pp. 704\u2013713. IEEE (2016)","DOI":"10.1109\/FOCS.2016.80"},{"key":"23_CR15","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1007\/PL00001601","volume":"9","author":"C Greenhill","year":"2000","unstructured":"Greenhill, C.: The complexity of counting colourings and independent sets in sparse graphs and hypergraphs. Comput. Complex. 9, 52\u201372 (2000)","journal-title":"Comput. Complex."},{"key":"23_CR16","doi-asserted-by":"publisher","first-page":"1557","DOI":"10.1137\/1.9781611975031.102","volume-title":"Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Nicholas J. A. Harvey","year":"2018","unstructured":"Harvey, N.J.A., Srivastava, P., Vondr\u00e1k, J.: Computing the independence polynomial: from the tree threshold down to the roots. In: Proceedings of the SODA 2018, pp. 1557\u20131576 (2018)"},{"key":"23_CR17","series-title":"Algorithms and Combinatorics","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1007\/978-3-662-12788-9_4","volume-title":"Probabilistic Methods for Algorithmic Discrete Mathematics","author":"M Jerrum","year":"1998","unstructured":"Jerrum, M.: Mathematical foundations of the Markov chain Monte Carlo method. In: Habib, M., McDiarmid, C., Ramirez-Alfonsin, J., Reed, B. (eds.) Probabilistic Methods for Algorithmic Discrete Mathematics. AC, vol. 16, pp. 116\u2013165. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/978-3-662-12788-9_4"},{"key":"23_CR18","series-title":"Lectures in Mathematics - ETH Z\u00fcrich","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. Lectures in Mathematics - ETH Z\u00fcrich. Birkh\u00e4user, Basel (2003)"},{"key":"23_CR19","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, 1149\u20131178 (1989)","journal-title":"SIAM J. Comput."},{"key":"23_CR20","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1145\/1008731.1008738","volume":"51","author":"M Jerrum","year":"2004","unstructured":"Jerrum, M., Sinclair, A., Vigoda, E.: A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. J. ACM 51, 671\u2013697 (2004)","journal-title":"J. ACM"},{"key":"23_CR21","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","volume":"43","author":"MR Jerrum","year":"1986","unstructured":"Jerrum, M.R., Valiant, L.G., Vazirani, V.V.: Random generation of combinatorial structures from a uniform distribution. Theoret. Comput. Sci. 43, 169\u2013188 (1986)","journal-title":"Theoret. Comput. Sci."},{"key":"23_CR22","unstructured":"Matthews, J.: Markov chains for sampling matchings, Ph.D. thesis, University of Edinburgh (2008)"},{"key":"23_CR23","unstructured":"Luby, M., Vigoda, E.: Approximately counting up to four. In: Proceedings of the STOC 1995, pp. 150\u2013159. ACM (1995)"},{"key":"23_CR24","doi-asserted-by":"publisher","first-page":"284","DOI":"10.1016\/0095-8956(80)90074-X","volume":"28","author":"GJ Minty","year":"1980","unstructured":"Minty, G.J.: On maximal independent sets of vertices in claw-free graphs. J. Comb. Theory Ser. B 28, 284\u2013304 (1980)","journal-title":"J. Comb. Theory Ser. B"},{"key":"23_CR25","doi-asserted-by":"publisher","first-page":"1893","DOI":"10.1137\/16M1101003","volume":"46","author":"V Patel","year":"2017","unstructured":"Patel, V., Regts, G.: Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials. SIAM J. Comput. 46, 1893\u20131919 (2017)","journal-title":"SIAM J. Comput."},{"key":"23_CR26","doi-asserted-by":"publisher","first-page":"777","DOI":"10.1137\/0212053","volume":"12","author":"JS Provan","year":"1983","unstructured":"Provan, J.S., Ball, M.O.: The complexity of counting cuts and of computing the probability that a graph is connected. SIAM J. Comput. 12, 777\u2013788 (1983)","journal-title":"SIAM J. Comput."},{"key":"23_CR27","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"35","author":"N Robertson","year":"1983","unstructured":"Robertson, N., Seymour, P.D.: Graph minors I: excluding a forest. J. Comb. Theory Ser. B 35, 39\u201361 (1983)","journal-title":"J. Comb. Theory Ser. B"},{"key":"23_CR28","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. Probab. Comput. 1, 351\u2013370 (1992)","journal-title":"Comb. Probab. Comput."},{"key":"23_CR29","doi-asserted-by":"crossref","unstructured":"Sly, A.: Computational transition at the uniqueness threshold. In: Proceedings of the FOCS 2010, pp. 287\u2013296. IEEE (2010)","DOI":"10.1109\/FOCS.2010.34"},{"key":"23_CR30","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1137\/S0097539797321602","volume":"31","author":"SP Vadhan","year":"2001","unstructured":"Vadhan, S.P.: The complexity of counting in sparse, regular, and planar graphs. SIAM J. Comput. 31, 398\u2013427 (2001)","journal-title":"SIAM J. Comput."},{"key":"23_CR31","doi-asserted-by":"crossref","unstructured":"Weitz, D.: Counting independent sets up to the tree threshold. In: Proceedings of the STOC 2006, pp. 140\u2013149. ACM (2006)","DOI":"10.1145\/1132516.1132538"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-30786-8_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,12,6]],"date-time":"2019-12-06T21:04:42Z","timestamp":1575666282000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-30786-8_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030307851","9783030307868"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-30786-8_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"12 September 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Vall de N\u00faria","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Spain","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 June 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 June 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"45","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2019a","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/wg2019.sau.thilikos.info\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Open","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":"87","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":"29","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":"33% - 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":"3.4","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":"1-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)"}}]}}