{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,2]],"date-time":"2025-05-02T04:15:16Z","timestamp":1746159316931,"version":"3.40.4"},"publisher-location":"Cham","reference-count":16,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319049205"},{"type":"electronic","value":"9783319049212"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-04921-2_23","type":"book-chapter","created":{"date-parts":[[2014,2,5]],"date-time":"2014-02-05T13:52:25Z","timestamp":1391608345000},"page":"285-296","source":"Crossref","is-referenced-by-count":4,"title":["Succinct Encodings of Graph Isomorphism"],"prefix":"10.1007","author":[{"given":"Bireswar","family":"Das","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Patrick","family":"Scharpfenecker","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jacobo","family":"Tor\u00e1n","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"23_CR1","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1145\/800061.808746","volume-title":"Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, STOC 1983","author":"L. Babai","year":"1983","unstructured":"Babai, L., Luks, E.M.: Canonical labeling of graphs. In: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, STOC 1983, pp. 171\u2013183. ACM Press, New York (1983)"},{"key":"23_CR2","doi-asserted-by":"crossref","unstructured":"Balc\u00e1zar, J.L., Lozano, A., Tor\u00e1n, J.: The Complexity of Algorithmic Problems on Succinct Instances. Computer Science, Research and Applications. Springer US (1992)","DOI":"10.1007\/978-1-4615-3422-8_30"},{"key":"23_CR3","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1145\/182591.182639","volume-title":"Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS 1994","author":"T. Eiter","year":"1994","unstructured":"Eiter, T., Gottlob, G., Mannila, H.: Adding disjunction to datalog (extended abstract). In: Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS 1994, pp. 267\u2013278. ACM Press, New York (1994)"},{"key":"23_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/BFb0028563","volume-title":"STACS 98","author":"J. Feigenbaum","year":"1998","unstructured":"Feigenbaum, J., Kannan, S., Vardi, M.Y., Viswanathan, M.: Complexity of Problems on Graphs Represented as OBDDs. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol.\u00a01373, pp. 216\u2013226. Springer, Heidelberg (1998)"},{"key":"23_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1007\/978-3-540-77050-3_28","volume-title":"FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science","author":"H. Fleischner","year":"2007","unstructured":"Fleischner, H., Mujuni, E., Paulusma, D., Szeider, S.: Covering Graphs with Few Complete Bipartite Subgraphs. In: Arvind, V., Prasad, S. (eds.) FSTTCS 2007. LNCS, vol.\u00a04855, pp. 340\u2013351. Springer, Heidelberg (2007)"},{"issue":"1","key":"23_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1996.0001","volume":"124","author":"L. Fortnow","year":"1996","unstructured":"Fortnow, L., Reingold, N.: PP Is Closed under Truth-Table Reductions. Information and Computation\u00a0124(1), 1\u20136 (1996)","journal-title":"Information and Computation"},{"issue":"1","key":"23_CR7","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1016\/j.ic.2005.02.002","volume":"198","author":"M. Galota","year":"2005","unstructured":"Galota, M., Vollmer, H.: Functions computable in polynomial space. Information and Computation\u00a0198(1), 56\u201370 (2005)","journal-title":"Information and Computation"},{"issue":"3","key":"23_CR8","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/S0019-9958(83)80004-7","volume":"56","author":"H. Galperin","year":"1983","unstructured":"Galperin, H., Wigderson, A.: Succinct representations of graphs. Information and Control\u00a056(3), 183\u2013198 (1983)","journal-title":"Information and Control"},{"key":"23_CR9","unstructured":"Jahanjou, H., Miles, E., Viola, E.: Local reductions (2013)"},{"key":"23_CR10","doi-asserted-by":"crossref","unstructured":"K\u00f6bler, J., Sch\u00f6ning, U., Tor\u00e1n, J.: The graph isomorphism problem: its structural complexity. Birkhauser (August 1994)","DOI":"10.1007\/978-1-4612-0333-9"},{"issue":"3","key":"23_CR11","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/S0019-9958(86)80009-2","volume":"71","author":"C.H. Papadimitriou","year":"1986","unstructured":"Papadimitriou, C.H., Yannakakis, M.: A note on succinct representations of graphs. Information and Control\u00a071(3), 181\u2013185 (1986)","journal-title":"Information and Control"},{"key":"23_CR12","unstructured":"Sch\u00f6ning, U., Tor\u00e1n, J.: The Satisfiability Problem: Algorithms and Analyses. Lehmanns Media (2013)"},{"key":"23_CR13","doi-asserted-by":"crossref","unstructured":"Toran, J.: On the hardness of graph isomorphism. In: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, pp. 180\u2013186 (2000)","DOI":"10.1109\/SFCS.2000.892080"},{"issue":"1","key":"23_CR14","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1007\/s00224-008-9159-1","volume":"47","author":"J. Tor\u00e1n","year":"2008","unstructured":"Tor\u00e1n, J.: Reductions to Graph Isomorphism. Theory of Computing Systems\u00a047(1), 288\u2013299 (2008)","journal-title":"Theory of Computing Systems"},{"issue":"5","key":"23_CR15","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/S0020-0190(97)00134-8","volume":"63","author":"H. Veith","year":"1997","unstructured":"Veith, H.: Languages represented by Boolean formulas. Information Processing Letters\u00a063(5), 251\u2013256 (1997)","journal-title":"Information Processing Letters"},{"key":"23_CR16","doi-asserted-by":"crossref","unstructured":"Veith, H.: How to encode a logical structure by an OBDD. In: Proceedings of the 13th IEEE Conference on Computational Complexity, pp. 122\u2013131. IEEE Comput. Soc. (1998)","DOI":"10.1109\/CCC.1998.694598"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-04921-2_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T19:39:39Z","timestamp":1746128379000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-04921-2_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319049205","9783319049212"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-04921-2_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}