{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:10:06Z","timestamp":1750295406256,"version":"3.41.0"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2017,6,7]],"date-time":"2017-06-07T00:00:00Z","timestamp":1496793600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["TO 200\/3-1"],"award-info":[{"award-number":["TO 200\/3-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2018,7]]},"DOI":"10.1007\/s00224-017-9787-4","type":"journal-article","created":{"date-parts":[[2017,6,7]],"date-time":"2017-06-07T01:45:50Z","timestamp":1496799950000},"page":"1125-1143","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Bounded-Depth Succinct Encodings and the Structure they Imply on Graphs"],"prefix":"10.1007","volume":"62","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2479-9158","authenticated-orcid":false,"given":"Patrick","family":"Scharpfenecker","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,6,7]]},"reference":[{"issue":"3","key":"9787_CR1","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/BF02579381","volume":"6","author":"N Alon","year":"1986","unstructured":"Alon, N.: Covering graphs by the minimum number of equivalence relations. Combinatorica 6(3), 201\u2013206 (1986). doi: 10.1007\/BF02579381","journal-title":"Combinatorica"},{"key":"9787_CR2","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1109\/SFCS.1986.15","volume-title":"Proceedings of the 27th Annual Symposium on Foundations of Computer Science, SFCS\u201986","author":"L Babai","year":"1986","unstructured":"Babai, L., Frankl, P., Simon, J.: Complexity classes in communication complexity theory Proceedings of the 27th Annual Symposium on Foundations of Computer Science, SFCS\u201986, pp 337\u2013347. IEEE Computer Society, Washington (1986), doi: 10.1109\/SFCS.1986.15"},{"key":"9787_CR3","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/978-1-4615-3422-8_30","volume-title":"The complexity of algorithmic problems on succinct instances. Computer Science, Research and Applications","author":"JL Balc\u00e1zar","year":"1992","unstructured":"Balc\u00e1zar, J.L., Lozano, A., Tor\u00e1n, J.: The complexity of algorithmic problems on succinct instances. Computer Science, Research and Applications, pp 351\u2013377. Springer, US (1992)"},{"issue":"11","key":"9787_CR4","doi-asserted-by":"publisher","first-page":"1264","DOI":"10.1016\/j.ic.2008.07.003","volume":"206","author":"M Chleb\u00edk","year":"2008","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: Approximation hardness of dominating set problems in bounded degree graphs. Inf. Comput. 206(11), 1264\u20131275 (2008). doi: 10.1016\/j.ic.2008.07.003","journal-title":"Inf. Comput."},{"issue":"4","key":"9787_CR5","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/S0022-0000(73)80028-5","volume":"7","author":"SA Cook","year":"1973","unstructured":"Cook, S.A.: A hierarchy for nondeterministic time complexity. J. Comput. Syst. Sci. 7(4), 343\u2013353 (1973). doi: 10.1016\/S0022-0000(73)80028-5","journal-title":"J. Comput. Syst. Sci."},{"key":"9787_CR6","doi-asserted-by":"publisher","unstructured":"Dahlhaus, E.: Reduction to NP-complete problems by interpretations Logic and Machines: Decision Problems and Complexity, Proceedings of the Symposium \u201cRekursive Kombinatorik\u201d held from May 23-28, 1983 at the Institut f\u00fcr Mathematische Logik und Grundlagenforschung der Universit\u00e4t M\u00fcnster\/Westfalen, pp. 357\u2013365 (1983), doi: 10.1007\/3-540-13331-3_51","DOI":"10.1007\/3-540-13331-3_51"},{"key":"9787_CR7","doi-asserted-by":"publisher","unstructured":"Das, B., Scharpfenecker, P., Tor\u00e1n, J.: CNF And DNF succinct graph encodings Information and Computation. doi: 10.1016\/j.ic.2016.06.009 (2016)","DOI":"10.1016\/j.ic.2016.06.009"},{"issue":"1","key":"9787_CR8","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/BF01300127","volume":"16","author":"N Eaton","year":"1996","unstructured":"Eaton, N., R\u00f6dl, V.: Graphs of small dimensions. Combinatorica 16(1), 59\u201385 (1996). doi: 10.1007\/BF01300127","journal-title":"Combinatorica"},{"key":"9787_CR9","unstructured":"Ebbinghaus, H., Flum, J.: Finite Model Theory. Perspectives in Mathematical Logic, Springer (2005)"},{"key":"9787_CR10","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1145\/182591.182639","volume-title":"Proceedings of the 13th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems - PODS\u201994","author":"T Eiter","year":"1994","unstructured":"Eiter, T., Gottlob, G., Mannila, H.: Adding disjunction to datalog (extended abstract) Proceedings of the 13th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems - PODS\u201994, pp 267\u2013278. ACM Press, New York (1994), doi: 10.1145\/182591.182639"},{"issue":"3","key":"9787_CR11","doi-asserted-by":"crossref","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. Inf. Control. 56(3), 183\u2013198 (1983)","journal-title":"Inf. Control."},{"issue":"3","key":"9787_CR12","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M Garey","year":"1976","unstructured":"Garey, M., Johnson, D., Stockmeyer, L.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1(3), 237\u2013267 (1976). doi: 10.1016\/0304-3975(76)90059-1","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9787_CR13","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the Complexity of k-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001). doi: 10.1006\/jcss.2000.1727","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"9787_CR14","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which Problems Have Strongly Exponential Complexity?. J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001). doi: 10.1006\/jcss.2001.1774","journal-title":"J. Comput. Syst. Sci."},{"issue":"6","key":"9787_CR15","doi-asserted-by":"publisher","first-page":"855","DOI":"10.1017\/S0963548306007620","volume":"15","author":"S Jukna","year":"2006","unstructured":"Jukna, S.: On graph complexity. Comb. Probab. Comput. 15(6), 855\u2013876 (2006). doi: 10.1017\/S0963548306007620","journal-title":"Comb. Probab. Comput."},{"issue":"10","key":"9787_CR16","doi-asserted-by":"publisher","first-page":"3399","DOI":"10.1016\/j.disc.2008.09.036","volume":"309","author":"S Jukna","year":"2009","unstructured":"Jukna, S.: On covering graphs by complete bipartite subgraphs. Discret. Math. 309(10), 3399\u20133403 (2009). doi: 10.1016\/j.disc.2008.09.036","journal-title":"Discret. Math."},{"issue":"1","key":"9787_CR17","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1002\/jgt.20367","volume":"61","author":"S Jukna","year":"2009","unstructured":"Jukna, S.: On set intersection representations of graphs. Journal of Graph Theory 61(1), 55\u201375 (2009). doi: 10.1002\/jgt.20367","journal-title":"Journal of Graph Theory"},{"issue":"2","key":"9787_CR18","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/0022-0000(82)90002-2","volume":"25","author":"SR Mahaney","year":"1982","unstructured":"Mahaney, S.R.: Sparse complete sets for NP: Solution of a Conjecture of Berman and Hartmanis. J. Comput. Syst. Sci. 25(2), 130\u2013143 (1982). doi: 10.1016\/0022-0000(82)90002-2","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"9787_CR19","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1017\/S0963548397003064","volume":"6","author":"V R\u00f6dl","year":"1997","unstructured":"R\u00f6dl, V., Ruci\u0144ski, A.: Bipartite coverings of graphs. Comb. Probab. Comput. 6(3), 349\u2013352 (1997). doi: 10.1017\/S0963548397003064","journal-title":"Comb. Probab. Comput."},{"issue":"1","key":"9787_CR20","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1145\/322047.322061","volume":"25","author":"JI Seiferas","year":"1978","unstructured":"Seiferas, J.I., Fischer, M.J., Meyer, A.R.: Separating nondeterministic time complexity classes. J. ACM 25(1), 146\u2013167 (1978). doi: 10.1145\/322047.322061","journal-title":"J. ACM"},{"issue":"2","key":"9787_CR21","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/BF01195200","volume":"27","author":"IA Stewart","year":"1994","unstructured":"Stewart, I.A.: On completeness for NP via projection translations. Mathematical Systems Theory 27(2), 125\u2013157 (1994). doi: 10.1007\/BF01195200","journal-title":"Mathematical Systems Theory"},{"issue":"5","key":"9787_CR22","doi-asserted-by":"crossref","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. Inf. Process. Lett. 63 (5), 251\u2013256 (1997)","journal-title":"Inf. Process. Lett."},{"key":"9787_CR23","doi-asserted-by":"crossref","unstructured":"Veith, H.: How to encode a logical structure by an OBDD Proceedings 13th IEEE Conference on Computational Complexity, pp 122\u2013131. IEEE Computer Society (1998)","DOI":"10.1109\/CCC.1998.694598"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9787-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9787-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9787-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:41:41Z","timestamp":1750293701000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9787-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,7]]},"references-count":23,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["9787"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9787-4","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2017,6,7]]}}}