{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T16:08:19Z","timestamp":1725552499455},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642121999"},{"type":"electronic","value":"9783642122002"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-12200-2_50","type":"book-chapter","created":{"date-parts":[[2010,4,21]],"date-time":"2010-04-21T09:53:05Z","timestamp":1271843585000},"page":"577-590","source":"Crossref","is-referenced-by-count":5,"title":["Some Observations on Holographic Algorithms"],"prefix":"10.1007","author":[{"given":"Leslie G.","family":"Valiant","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"50_CR1","unstructured":"Barbanchon, R.: Reductions fines entre probl\u00e8mes NP-complets, PhD Thesis, Universit\u00e9 de Caen Basse-Normandie (2003)"},{"issue":"1-3","key":"50_CR2","doi-asserted-by":"publisher","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\u00a0319(1-3), 455\u2013482 (2004)","journal-title":"Theoretical Computer Science"},{"key":"50_CR3","doi-asserted-by":"publisher","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.\u00a029, 387\u2013400 (1999)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"50_CR4","first-page":"3","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\u00a01(1), 3\u201336 (2007)","journal-title":"International Journal of Software and Informatics"},{"issue":"1","key":"50_CR5","doi-asserted-by":"publisher","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\u00a045(1), 108\u2013132 (2009)","journal-title":"Theory of Computing Systems"},{"key":"50_CR6","doi-asserted-by":"crossref","unstructured":"Cai, J.-Y., Lu, P.: Holographic algorithms: from art to science. In: STOC 2007, pp. 401\u2013410 (2007)","DOI":"10.1145\/1250790.1250850"},{"issue":"18","key":"50_CR7","doi-asserted-by":"publisher","first-page":"1618","DOI":"10.1016\/j.tcs.2008.12.047","volume":"410","author":"J.-Y. Cai","year":"2009","unstructured":"Cai, J.-Y., Lu, P.: Holographic algorithms: The power of dimensionality resolved. Theor. Comput. Sci.\u00a0410(18), 1618\u20131628 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"50_CR8","doi-asserted-by":"crossref","unstructured":"Cai, J.-Y., Lu, P., Xia, M.: Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness. In: FOCS, pp. 644\u2013653 (2008)","DOI":"10.1109\/FOCS.2008.34"},{"key":"50_CR9","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: The complexity of theorem proving procedures. In: Proceedings of the 3rd ACM STOC, pp. 151\u2013158 (1971)","DOI":"10.1145\/800157.805047"},{"key":"50_CR10","doi-asserted-by":"crossref","unstructured":"Escoffier, B., Gourves, L., Monnot, J.: Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs. Journal of Discrete Algorithms (2009)","DOI":"10.1016\/j.jda.2009.01.005"},{"key":"50_CR11","doi-asserted-by":"crossref","unstructured":"Fernau, H., Manlove, D.: Vertex and edge covers with clustering properties: Complexity and algorithms. Journal of Discrete Algorithms (2009)","DOI":"10.1016\/j.jda.2008.09.007"},{"key":"50_CR12","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"M.R. Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: The rectilinear steiner tree problem is NP complete. SIAM Journal of Applied Mathematics\u00a032, 826\u2013834 (1977)","journal-title":"SIAM Journal of Applied Mathematics"},{"key":"50_CR13","volume-title":"Computer and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computer and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, New York (1979)"},{"issue":"4","key":"50_CR14","doi-asserted-by":"publisher","first-page":"1142","DOI":"10.1137\/S0097539793304601","volume":"27","author":"H.B. Hunt III","year":"1998","unstructured":"Hunt III, H.B., Marathe, M.V., Radhakrishnan, V., Stearns, R.E.: The Complexity of Planar Counting Problems. SIAM J. Comput.\u00a027(4), 1142\u20131167 (1998)","journal-title":"SIAM J. Comput."},{"issue":"1-2","key":"50_CR15","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/BF01010403","volume":"48","author":"M.R. Jerrum","year":"1987","unstructured":"Jerrum, M.R.: Two-dimensional monomer-dimer systems are computationally intractable. J. Statist. Phys.\u00a048(1-2), 121\u2013134 (1987)","journal-title":"J. Statist. Phys."},{"key":"50_CR16","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85\u2013104. Plenum Press, New York (1972)"},{"issue":"1","key":"50_CR17","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1145\/990518.990519","volume":"7","author":"R.E. Ladner","year":"1975","unstructured":"Ladner, R.E.: The Circuit Value Problem is Log Space Complete for P. SIGACT NEWS\u00a07(1), 18\u201320 (1975)","journal-title":"SIGACT NEWS"},{"issue":"4","key":"50_CR18","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1016\/S0252-9602(17)30520-9","volume":"19","author":"D.M. 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.\u00a019(4), 375\u2013381 (1999)","journal-title":"Acta Math. Sci."},{"key":"50_CR19","doi-asserted-by":"publisher","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.\u00a011, 329\u2013343 (1982)","journal-title":"SIAM J. Comput."},{"key":"50_CR20","first-page":"120","volume":"1","author":"O.B. Lupanov","year":"1958","unstructured":"Lupanov, O.B.: A method of circuit synthesis. Izv. VUZ Radiofiz\u00a01, 120\u2013140 (1958)","journal-title":"Izv. VUZ Radiofiz"},{"key":"50_CR21","first-page":"999","volume":"7","author":"E.I. Neciporuk","year":"1966","unstructured":"Neciporuk, E.I.: A Boolean Function. Sov. Math. Dokl.\u00a07, 999\u20131000 (1966)","journal-title":"Sov. Math. Dokl."},{"key":"50_CR22","unstructured":"Speckenmeyer, E.: Untersuchungen zum Feedback Vertex Set Problem in ungerichteten Graphen. PhD Thesis, Universit\u00e4t Paderborn (1983)"},{"issue":"3","key":"50_CR23","doi-asserted-by":"publisher","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\u00a012(3), 405\u2013412 (1988)","journal-title":"Journal of Graph Theory"},{"key":"50_CR24","doi-asserted-by":"publisher","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\u00a072, 355\u2013360 (1988)","journal-title":"Discrete Mathematics"},{"key":"50_CR25","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theoretical Computer Science\u00a08, 189\u2013201 (1979)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"50_CR26","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Computing\u00a08(3), 410\u2013421 (1979)","journal-title":"SIAM J. Computing"},{"key":"50_CR27","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1109\/FOCS.2004.34","volume-title":"Proc. 45th Annual IEEE Symposium on Foundations of Computer Science","author":"L.G. Valiant","year":"2004","unstructured":"Valiant, L.G.: Holographic algorithms (extended abstract). In: Proc. 45th Annual IEEE Symposium on Foundations of Computer Science, October 17-19, pp. 306\u2013315. IEEE Press, Los Alamitos (2004)"},{"key":"50_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/11533719_1","volume-title":"Computing and Combinatorics","author":"L.G. Valiant","year":"2005","unstructured":"Valiant, L.G.: Completeness for parity problems. In: Wang, L. (ed.) COCOON 2005. LNCS, vol.\u00a03595, pp. 1\u20139. Springer, Heidelberg (2005)"},{"key":"50_CR29","first-page":"509","volume-title":"Proc. 47th Annual IEEE Symposium on Foundations of Computer Science","author":"L.G. Valiant","year":"2006","unstructured":"Valiant, L.G.: Accidental algorithms. In: Proc. 47th Annual IEEE Symposium on Foundations of Computer Science, October 22-24, pp. 509\u2013517. IEEE Press, Los Alamitos (2006)"},{"issue":"5","key":"50_CR30","doi-asserted-by":"publisher","first-page":"1565","DOI":"10.1137\/070682575","volume":"37","author":"L.G. Valiant","year":"2008","unstructured":"Valiant, L.G.: Holographic algorithms. SIAM J. on Computing\u00a037(5), 1565\u20131594 (2008); Earlier version: Electronic Colloquium on Computational Complexity, Report TR05-099 (2005)","journal-title":"SIAM J. on Computing"},{"issue":"1","key":"50_CR31","doi-asserted-by":"publisher","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.\u00a0384(1), 111\u2013125 (2007)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","LATIN 2010: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-12200-2_50.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T21:51:19Z","timestamp":1606168279000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-12200-2_50"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642121999","9783642122002"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-12200-2_50","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}