{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,2]],"date-time":"2023-10-02T14:00:08Z","timestamp":1696255208193},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2017,8,29]],"date-time":"2017-08-29T00:00:00Z","timestamp":1503964800000},"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":["comput. complex."],"published-print":{"date-parts":[[2018,9]]},"DOI":"10.1007\/s00037-017-0160-4","type":"journal-article","created":{"date-parts":[[2017,8,29]],"date-time":"2017-08-29T10:57:57Z","timestamp":1504004277000},"page":"351-374","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Some observations on holographic algorithms"],"prefix":"10.1007","volume":"27","author":[{"given":"Leslie G.","family":"Valiant","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,8,29]]},"reference":[{"issue":"1\u20133","key":"160_CR1","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1016\/j.tcs.2004.02.003","volume":"319","author":"R Barbanchon","year":"2004","unstructured":"Barbanchon, R.: On unique graph 3-colorability and parsimonious reductions in the plane. Theoretical Computer Science 319(1\u20133), 455\u2013482 (2004)","journal-title":"Theoretical Computer Science"},{"key":"160_CR2","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1137\/S0097539798338175","volume":"29","author":"R Bubley","year":"1999","unstructured":"Bubley, R.; Dyer, M.; Greenhill, C.; Jerrum, M.: On approximately counting colourings of small degree graphs. SIAM J. Comput 29, 387\u2013400 (1999)","journal-title":"SIAM J. Comput"},{"key":"160_CR3","first-page":"1","volume":"1","author":"J-Y Cai","year":"2007","unstructured":"Cai, J.-Y.; Choudhary, V.: Some Results on Matchgates and Holographic Algorithms. International Journal of Software and Informatics 1, 1 (2007)","journal-title":"International Journal of Software and Informatics"},{"issue":"1","key":"160_CR4","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1007\/s00224-007-9092-8","volume":"45","author":"J-Y Cai","year":"2009","unstructured":"Cai, J.-Y.; Choudhary, V.; Lu, P.: On the Theory of Matchgate Computations. Theory of Computing Systems 45(1), 108\u2013132 (2009)","journal-title":"Theory of Computing Systems"},{"key":"160_CR5","doi-asserted-by":"crossref","first-page":"167","DOI":"10.4086\/toc.2014.v010a007","volume":"10","author":"J-Y Cai","year":"2014","unstructured":"Cai, J.-Y.; Gorenstein, A.: Matchgates Revisited. Theory of Computing 10, 167\u2013197 (2014)","journal-title":"Theory of Computing"},{"key":"160_CR6","unstructured":"J.-Y. Cai, H.\u00a0Guo & T.\u00a0Williams (2014). The Complexity of Counting Edge Colorings and a Dichotomy for Some Higher Domain Holant Problems. FOCS 601\u2013610."},{"key":"160_CR7","unstructured":"J.-Y. Cai, P.\u00a0Lu & M.\u00a0Xia (2008). Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness. FOCS 644\u2013653."},{"key":"160_CR8","unstructured":"S.\u00a0Chen (2016). Basis collapse for holographic algorithms over all domain sizes. STOC 776\u2013789."},{"issue":"2","key":"160_CR9","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/j.jda.2008.09.007","volume":"7","author":"H Fernau","year":"2009","unstructured":"Fernau, H.; Manlove, D.: Vertex and edge covers with clustering properties: Complexity and algorithms. Journal of Discrete Algorithms 7(2), 149\u2013167 (2009)","journal-title":"Journal of Discrete Algorithms"},{"key":"160_CR10","doi-asserted-by":"crossref","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"MR Garey","year":"1977","unstructured":"Garey, M.R.; Johnson, D.S.: The rectilinear Steiner tree problem is NP complete. SIAM Journal of Applied Mathematics 32, 826\u2013834 (1977)","journal-title":"SIAM Journal of Applied Mathematics"},{"key":"160_CR11","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R.; Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, W. H (1979)"},{"issue":"4","key":"160_CR12","doi-asserted-by":"crossref","first-page":"1142","DOI":"10.1137\/S0097539793304601","volume":"27","author":"HB Hunt","year":"1998","unstructured":"Hunt, H.B.; Marathe, M.V.; Radhakrishnan, V.; Stearns, R.E.: The Complexity of Planar Counting Problems. SIAM J. Comput 27(4), 1142\u20131167 (1998)","journal-title":"SIAM J. Comput"},{"issue":"1\u20132","key":"160_CR13","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/BF01010403","volume":"48","author":"MR Jerrum","year":"1987","unstructured":"Jerrum, M.R.: Two-dimensional monomer-dimer systems are computationally intractable. J. Statist. Phys 48(1\u20132), 121\u2013134 (1987)","journal-title":"J. Statist. Phys"},{"key":"160_CR14","doi-asserted-by":"crossref","unstructured":"R.\u00a0M. Karp (1972). Reducibility among combinatorial problems. In Complexity of Computer Computations, R.\u00a0E. Miller & J.\u00a0W. Thatcher, editors, 85\u2013104. Plenum Press.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"issue":"1","key":"160_CR15","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1145\/990518.990519","volume":"7","author":"RE Ladner","year":"1975","unstructured":"Ladner, R.E.: The circuit value problem is Log Space Complete for P. SIGACT NEWS 7(1), 18\u201320 (1975)","journal-title":"SIGACT NEWS"},{"issue":"4","key":"160_CR16","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1016\/S0252-9602(17)30520-9","volume":"19","author":"DM Li","year":"1999","unstructured":"Li, D.M.; Liu, Y.P.: A polynomial algorithm for finding the minimum feedback vertex set of a 3-regular simple graph. Acta Math. Sci 19(4), 375\u2013381 (1999)","journal-title":"Acta Math. Sci"},{"key":"160_CR17","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1137\/0211025","volume":"11","author":"D Lichtenstein","year":"1982","unstructured":"Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput 11, 329\u2013343 (1982)","journal-title":"SIAM J. Comput"},{"key":"160_CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-3975(03)00080-X","volume":"304","author":"M Li\u015bkiewicz","year":"2003","unstructured":"Li\u015bkiewicz, M.; Ogihara, M.; Toda, S.: The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes. Theoretical Computer Science 304, 1 (2003)","journal-title":"Theoretical Computer Science"},{"key":"160_CR19","first-page":"120","volume":"1","author":"OB Lupanov","year":"1958","unstructured":"Lupanov, O.B.: A method of circuit synthesis. Izv. VUZ Radiofiz 1, 120\u2013140 (1958)","journal-title":"Izv. VUZ Radiofiz"},{"key":"160_CR20","first-page":"999","volume":"7","author":"EI Neciporuk","year":"1966","unstructured":"Neciporuk, E.I.: A Boolean Function. Sov. Math. Dokl 7, 999\u20131000 (1966)","journal-title":"A Boolean Function. Sov. Math. Dokl"},{"key":"160_CR21","unstructured":"E.\u00a0Speckenmeyer (1983). Untersuchungen zum Feedback Vertex Set Problem in ungerichteten Graphen. Ph.D. thesis, Universit\u00e4t Paderborn."},{"issue":"3","key":"160_CR22","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1002\/jgt.3190120311","volume":"12","author":"E Speckenmeyer","year":"1988","unstructured":"Speckenmeyer, E.: On feedback vertex sets and nonseparating independent sets in cubic graphs. Journal of Graph Theory 12(3), 405\u2013412 (1988)","journal-title":"Journal of Graph Theory"},{"key":"160_CR23","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1016\/0012-365X(88)90226-9","volume":"72","author":"S Ueno","year":"1988","unstructured":"Ueno, S.; Kajitani, Y.; Gotoh, S.: On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three. Discrete Mathematics 72, 355\u2013360 (1988)","journal-title":"Discrete Mathematics"},{"issue":"2","key":"160_CR24","doi-asserted-by":"crossref","first-page":"398","DOI":"10.1137\/S0097539797321602","volume":"31","author":"S Vadhan","year":"2001","unstructured":"Vadhan, S.: The Complexity of Counting in Sparse, Regular, and Planar Graphs. SIAM Journal on Computing 31(2), 398\u2013427 (2001)","journal-title":"SIAM Journal on Computing"},{"key":"160_CR25","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theoretical Computer Science 8, 189\u2013201 (1979a)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"160_CR26","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"LG Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Computing 8(3), 410\u2013421 (1979b)","journal-title":"SIAM J. Computing"},{"issue":"1","key":"160_CR27","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1016\/S0304-3975(01)00325-5","volume":"289","author":"LG Valiant","year":"2002","unstructured":"Valiant, L.G.: Expressiveness of matchgates. Theoretical Computer Science 289(1), 457\u2013471 (2002)","journal-title":"Theoretical Computer Science"},{"key":"160_CR28","doi-asserted-by":"crossref","unstructured":"L.\u00a0G. Valiant (2004). Holographic algorithms (extended abstract). In Proc. 45th Annual IEEE Symposium on Foundations of Computer Science, 17\u201319. Oct, Rome, Italy, IEEE Press, 306\u2013315.","DOI":"10.1109\/FOCS.2004.34"},{"key":"160_CR29","doi-asserted-by":"crossref","unstructured":"L.\u00a0G. Valiant (2005). Completeness for parity problems. In Proc. 11th International Computing and Combinatorics Conference, Aug, Kunming, China, LNCS, Vol. 3959, 1\u20139, 16\u201319.","DOI":"10.1007\/11533719_1"},{"key":"160_CR30","unstructured":"L.\u00a0G. Valiant (2006). Accidental algorithms. In Proc. 47th Annual IEEE Symposium on Foundations of Computer Science, 22\u201324. Oct, Berkeley, CA, IEEE Press, 509\u2013517."},{"key":"160_CR31","doi-asserted-by":"crossref","unstructured":"L.\u00a0G. Valiant (2008). Holographic algorithms. SIAM J. on Computing 37(5), 1565\u20131594. (Earlier version: Electronic Colloquium on Computational Complexity, Report TR-05-099, 2005).","DOI":"10.1137\/070682575"},{"key":"160_CR32","unstructured":"M.\u00a0Xia (2016). Base collapse of holographic algorithms. STOC 790\u2013799."},{"issue":"1","key":"160_CR33","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/j.tcs.2007.05.023","volume":"384","author":"M Xia","year":"2007","unstructured":"Xia, M.; Zhang, P.; Zhao, W.: Computational complexity of counting problems on 3-regular planar graphs. Theor. Comput. Sci 384(1), 111\u2013125 (2007)","journal-title":"Theor. Comput. Sci"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-017-0160-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-017-0160-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-017-0160-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,2]],"date-time":"2019-10-02T21:53:57Z","timestamp":1570053237000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-017-0160-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,29]]},"references-count":33,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,9]]}},"alternative-id":["160"],"URL":"https:\/\/doi.org\/10.1007\/s00037-017-0160-4","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,8,29]]}}}