{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,5,31]],"date-time":"2024-05-31T07:54:56Z","timestamp":1717142096257},"reference-count":34,"publisher":"Elsevier BV","issue":"6","license":[{"start":{"date-parts":[[2016,9,1]],"date-time":"2016-09-01T00:00:00Z","timestamp":1472688000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2020,9,1]],"date-time":"2020-09-01T00:00:00Z","timestamp":1598918400000},"content-version":"vor","delay-in-days":1461,"URL":"http:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["FP7\/2007\u20132013"],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"ERC","doi-asserted-by":"publisher","award":["334828"],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1219278"],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[2016,9]]},"DOI":"10.1016\/j.jcss.2016.04.001","type":"journal-article","created":{"date-parts":[[2016,4,14]],"date-time":"2016-04-14T23:31:31Z","timestamp":1460676691000},"page":"1144-1160","update-policy":"http:\/\/dx.doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":3,"title":["Approximately counting locally-optimal structures"],"prefix":"10.1016","volume":"82","author":[{"given":"Leslie Ann","family":"Goldberg","sequence":"first","affiliation":[]},{"given":"Rob","family":"Gysel","sequence":"additional","affiliation":[]},{"given":"John","family":"Lapinskas","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"issue":"3","key":"10.1016\/j.jcss.2016.04.001_br0010","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1142\/S0129054100000211","article-title":"Generating all the minimal separators of a graph","volume":"11","author":"Berry","year":"2000","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"2","key":"10.1016\/j.jcss.2016.04.001_br0020","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/j.dam.2004.01.008","article-title":"Tree decompositions with small cost","volume":"145","author":"Bodlaender","year":"2005","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"10.1016\/j.jcss.2016.04.001_br0030","doi-asserted-by":"crossref","first-page":"12:1","DOI":"10.1145\/2390176.2390188","article-title":"On exact algorithms for treewidth","volume":"9","author":"Bodlaender","year":"2012","journal-title":"ACM Trans. Algorithms"},{"issue":"3","key":"10.1016\/j.jcss.2016.04.001_br0040","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1093\/comjnl\/bxm037","article-title":"Combinatorial optimization on graphs of bounded treewidth","volume":"51","author":"Bodlaender","year":"2008","journal-title":"Comput. J."},{"issue":"1","key":"10.1016\/j.jcss.2016.04.001_br0050","doi-asserted-by":"crossref","first-page":"212","DOI":"10.1137\/S0097539799359683","article-title":"Treewidth and minimum fill-in: grouping the minimal separators","volume":"31","author":"Bouchitt\u00e9","year":"2001","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"10.1016\/j.jcss.2016.04.001_br0060","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/S0304-3975(01)00007-X","article-title":"Listing all potential maximal cliques of a graph","volume":"276","author":"Bouchitt\u00e9","year":"2002","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/j.jcss.2016.04.001_br0070","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1016\/j.ejc.2014.08.030","article-title":"The graph formulation of the union-closed sets conjecture","volume":"43","author":"Bruhn","year":"2015","journal-title":"Eur. J. Comb."},{"key":"10.1016\/j.jcss.2016.04.001_br0080","series-title":"Twelfth Annual IEEE Conference on Computational Complexity","first-page":"262","article-title":"A short guide to approximation preserving reductions","author":"Crescenzi","year":"1997"},{"key":"10.1016\/j.jcss.2016.04.001_br0090","article-title":"Graph Theory","volume":"vol. 173","author":"Diestel","year":"2012"},{"issue":"3","key":"10.1016\/j.jcss.2016.04.001_br0100","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1007\/s00453-003-1073-y","article-title":"The relative complexity of approximate counting problems","volume":"38","author":"Dyer","year":"2004","journal-title":"Algorithmica"},{"issue":"3","key":"10.1016\/j.jcss.2016.04.001_br0110","doi-asserted-by":"crossref","first-page":"1058","DOI":"10.1137\/050643350","article-title":"Exact algorithms for treewidth and minimum fill-in","volume":"38","author":"Fomin","year":"2008","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.jcss.2016.04.001_br0120","series-title":"27th International Symposium on Theoretical Aspects of Computer Science","first-page":"383","article-title":"Finding induced subgraphs via minimal triangulations","author":"Fomin","year":"2010"},{"issue":"3","key":"10.1016\/j.jcss.2016.04.001_br0130","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1007\/s00493-012-2536-z","article-title":"Treewidth computation and extremal combinatorics","volume":"32","author":"Fomin","year":"2012","journal-title":"Combinatorica"},{"key":"10.1016\/j.jcss.2016.04.001_br0140","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1016\/j.tcs.2014.03.013","article-title":"A revisit of the scheme for computing treewidth and minimum fill-in","volume":"531","author":"Furuse","year":"2014","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/j.jcss.2016.04.001_br0150","series-title":"Efficient Algorithms for Listing Combinatorial Structures","author":"Goldberg","year":"1993"},{"key":"10.1016\/j.jcss.2016.04.001_br0160","series-title":"Automata, Languages, and Programming: 42nd International Colloquium","first-page":"654","article-title":"Approximately counting locally-optimal structures","author":"Goldberg","year":"2015"},{"issue":"1","key":"10.1016\/j.jcss.2016.04.001_br0170","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1017\/S096354830600767X","article-title":"The complexity of ferromagnetic Ising with local fields","volume":"16","author":"Goldberg","year":"2007","journal-title":"Comb. Probab. Comput."},{"issue":"5","key":"10.1016\/j.jcss.2016.04.001_br0180","doi-asserted-by":"crossref","DOI":"10.1145\/2371656.2371660","article-title":"Approximating the partition function of the ferromagnetic Potts model","volume":"59","author":"Goldberg","year":"2012","journal-title":"J. ACM"},{"issue":"2","key":"10.1016\/j.jcss.2016.04.001_br0190","doi-asserted-by":"crossref","DOI":"10.1145\/2600917","article-title":"The complexity of approximately counting tree homomorphisms","volume":"2","author":"Goldberg","year":"2014","journal-title":"ACM Trans. Comput. Theory"},{"key":"10.1016\/j.jcss.2016.04.001_br0200","author":"Gysel"},{"key":"10.1016\/j.jcss.2016.04.001_br0210","series-title":"Proceedings of the 8th International Conference on Language and Automata Theory and Applications","first-page":"421","article-title":"Minimal triangulation algorithms for perfect phylogeny problems","volume":"vol. 8370","author":"Gysel","year":"2014"},{"issue":"1","key":"10.1016\/j.jcss.2016.04.001_br0220","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/0022-0000(88)90046-3","article-title":"How easy is local search?","volume":"37","author":"Johnson","year":"1988","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"10.1016\/j.jcss.2016.04.001_br0230","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/0196-6774(92)90012-2","article-title":"Generation of maximum independent sets of a bipartite graph and maximum cliques of a circular-arc graph","volume":"13","author":"Kashiwabara","year":"1992","journal-title":"J. Algorithms"},{"key":"10.1016\/j.jcss.2016.04.001_br0240","series-title":"Computing and Combinatorics \u2013 17th Annual International Conference","first-page":"13","article-title":"Dominating set counting in graph classes","author":"Kijima","year":"2011"},{"key":"10.1016\/j.jcss.2016.04.001_br0250","doi-asserted-by":"crossref","first-page":"605","DOI":"10.1137\/S009753979427087X","article-title":"Listing all minimal separators of a graph","volume":"27","author":"Kloks","year":"1998","journal-title":"SIAM J. Comput."},{"issue":"7","key":"10.1016\/j.jcss.2016.04.001_br0260","doi-asserted-by":"crossref","first-page":"820","DOI":"10.1016\/j.dam.2009.10.007","article-title":"On the complexity of computing treelength","volume":"158","author":"Lokshtanov","year":"2010","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"10.1016\/j.jcss.2016.04.001_br0270","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1137\/0220004","article-title":"Simple local search problems that are hard to solve","volume":"20","author":"Sch\u00e4ffer","year":"1991","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"10.1016\/j.jcss.2016.04.001_br0280","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/S0304-3975(97)83809-1","article-title":"Efficient enumeration of all minimal separators in a graph","volume":"180","author":"Shen","year":"1997","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/j.jcss.2016.04.001_br0290","series-title":"Introduction to the Theory of Computation","author":"Sipser","year":"2005"},{"issue":"15","key":"10.1016\/j.jcss.2016.04.001_br0300","doi-asserted-by":"crossref","first-page":"1660","DOI":"10.1016\/j.dam.2010.05.013","article-title":"Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph","volume":"158","author":"Takata","year":"2010","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"10.1016\/j.jcss.2016.04.001_br0310","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1137\/0206036","article-title":"A new algorithm for generating all the maximal independent sets","volume":"6","author":"Tsukiyama","year":"1977","journal-title":"SIAM J. Comput."},{"issue":"2","key":"10.1016\/j.jcss.2016.04.001_br0320","doi-asserted-by":"crossref","first-page":"398","DOI":"10.1137\/S0097539797321602","article-title":"The complexity of counting in sparse, regular, and planar graphs","volume":"31","author":"Vadhan","year":"2001","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10.1016\/j.jcss.2016.04.001_br0330","doi-asserted-by":"crossref","first-page":"73","DOI":"10.4064\/fm-21-1-73-84","article-title":"Planar graphs","volume":"21","author":"Whitney","year":"1933","journal-title":"Fundam. Math."},{"issue":"6","key":"10.1016\/j.jcss.2016.04.001_br0340","doi-asserted-by":"crossref","first-page":"1293","DOI":"10.1137\/S0097539794266407","article-title":"On unapproximable versions of NP-complete problems","volume":"25","author":"Zuckerman","year":"1996","journal-title":"SIAM J. Comput."}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000016300137?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000016300137?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2021,3,12]],"date-time":"2021-03-12T00:24:05Z","timestamp":1615508645000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0022000016300137"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,9]]},"references-count":34,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2016,9]]}},"alternative-id":["S0022000016300137"],"URL":"http:\/\/dx.doi.org\/10.1016\/j.jcss.2016.04.001","relation":{},"ISSN":["0022-0000"],"issn-type":[{"value":"0022-0000","type":"print"}],"subject":[],"published":{"date-parts":[[2016,9]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Approximately counting locally-optimal structures","name":"articletitle","label":"Article Title"},{"value":"Journal of Computer and System Sciences","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.jcss.2016.04.001","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2016 Elsevier Inc.","name":"copyright","label":"Copyright"}]}}
