{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:01Z","timestamp":1740109381776,"version":"3.37.3"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2023,8,15]],"date-time":"2023-08-15T00:00:00Z","timestamp":1692057600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,8,15]],"date-time":"2023-08-15T00:00:00Z","timestamp":1692057600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2023,12]]},"DOI":"10.1007\/s00224-023-10141-z","type":"journal-article","created":{"date-parts":[[2023,8,15]],"date-time":"2023-08-15T07:01:50Z","timestamp":1692082910000},"page":"1156-1196","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Implicit Representation of Relations"],"prefix":"10.1007","volume":"67","author":[{"given":"Vladan","family":"Glon\u010d\u00e1k","sequence":"first","affiliation":[]},{"given":"Jarl Emil Erla","family":"Munkstrup","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3488-9392","authenticated-orcid":false,"given":"Jakob","family":"Grue Simonsen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,8,15]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Alstrup, S., Dahlgaard, S., Knudsen, M.B.T.: Optimal induced universal graphs and adjacency labeling for trees. J. ACM. 64(4), 27:1\u201327:22 (2017)","key":"10141_CR1","DOI":"10.1145\/3088513"},{"unstructured":"Alstrup, S., Dahlgaard, S., Knudsen, M.B.T., Porat, E.: Sublinear distance labeling. In: 24th Annual european symposium on algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, pp. 5:1\u20135:15 (2016)","key":"10141_CR2"},{"unstructured":"Alstrup, S., G\u00f8rtz, I.L., Halvorsen, E.B., Porat, E.: Distance labeling schemes for trees. In: 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pp. 132:1\u2013132:16 (2016)","key":"10141_CR3"},{"issue":"1","key":"10141_CR4","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1137\/16M1105967","volume":"33","author":"S Alstrup","year":"2019","unstructured":"Alstrup, S., Kaplan, H., Thorup, M., Zwick, U.: Adjacency labeling schemes and induced-universal graphs. SIAM J. Discrete Math. 33(1), 116\u2013137 (2019)","journal-title":"SIAM J. Discrete Math."},{"key":"10141_CR5","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511608650","volume-title":"The theory of partitions","author":"GE Andrews","year":"1984","unstructured":"Andrews, G.E.: The theory of partitions. Cambridge University Press, Encyclopedia of mathematics and its applications (1984)"},{"issue":"1","key":"10141_CR6","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1145\/320064.320066","volume":"4","author":"C Beeri","year":"1979","unstructured":"Beeri, C., Bernstein, P.A.: Computational problems related to the design of normal form relational schemas. ACM Transactions on Database Systems (TODS) 4(1), 30\u201359 (1979)","journal-title":"ACM Transactions on Database Systems (TODS)"},{"key":"10141_CR7","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1145\/210197.210198","volume":"20","author":"L B\u00e6kgaard","year":"1995","unstructured":"B\u00e6kgaard, L., Mark, L.: Incremental computation of nested relational query expressions. ACM Trans. Database Syst. 20, 111\u2013148 (1995)","journal-title":"ACM Trans. Database Syst."},{"key":"10141_CR8","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1109\/TIT.1966.1053860","volume":"12","author":"M Breuer","year":"1966","unstructured":"Breuer, M.: Coding the vertexes of a graph. IEEE Trans. Inf. Theor. 12, 148\u2013153 (1966)","journal-title":"IEEE Trans. Inf. Theor."},{"issue":"3","key":"10141_CR9","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1016\/0022-247X(67)90082-0","volume":"20","author":"MA Breuer","year":"1967","unstructured":"Breuer, M.A., Folkman, J.: An unexpected result in coding the vertices of a graph. J. Math. Anal. Appl. 20(3), 583\u2013600 (1967)","journal-title":"J. Math. Anal. Appl."},{"doi-asserted-by":"crossref","unstructured":"Brodal, G.S., Fagerberg, R.: Dynamic representation of sparse graphs. In: Algorithms and data structures, 6th International Workshop, WADS \u201999, Vancouver, British Columbia, Canada, August 11-14, 1999, Proceedings, pp. 342\u2013351 (1999)","key":"10141_CR10","DOI":"10.1007\/3-540-48447-7_34"},{"key":"10141_CR11","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1145\/1272743.1272748","volume":"32","author":"B Cao","year":"2007","unstructured":"Cao, B., Badia, A.: Sql query optimization through nested relational algebra. ACM Trans. Database Syst. 32, 18 (2007)","journal-title":"ACM Trans. Database Syst."},{"unstructured":"Chandoo, M.: On the implicit graph conjecture. In: P. Faliszewski, A. Muscholl, R. Niedermeier (eds.) 41st International symposium on mathematical foundations of computer science, MFCS 2016, August 22-26, 2016 - Krak\u00f3w, Poland, LIPIcs, vol. 58, pp. 23:1\u201323:13. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016)","key":"10141_CR12"},{"unstructured":"Chandoo, M.: Computational complexity aspects of implicit graph representations. Ph.D. thesis, Leibniz Universit\u00e4t Hannover (2018)","key":"10141_CR13"},{"issue":"3\u20134","key":"10141_CR14","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1007\/s00453-010-9478-x","volume":"62","author":"V Chepoi","year":"2012","unstructured":"Chepoi, V., Dragan, F.F., Estellon, B., Habib, M., Vax\u00e8s, Y., Xiang, Y.: Additive spanners and distance and routing labeling schemes for hyperbolic graphs. Algorithmica 62(3\u20134), 713\u2013732 (2012)","journal-title":"Algorithmica"},{"issue":"2","key":"10141_CR15","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.jalgor.2004.07.011","volume":"61","author":"V Chepoi","year":"2006","unstructured":"Chepoi, V., Dragan, F.F., Vax\u00e8s, Y.: Distance and routing labeling schemes for non-positively curved plane graphs. J. Algorithms 61(2), 60\u201388 (2006)","journal-title":"J. Algorithms"},{"issue":"1","key":"10141_CR16","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1002\/jgt.22469","volume":"93","author":"V Chepoi","year":"2020","unstructured":"Chepoi, V., Labourel, A., Ratel, S.: On density of subgraphs of cartesian products. J. Graph Theor. 93(1), 64\u201387 (2020)","journal-title":"J. Graph Theor."},{"unstructured":"Chin, L.H., Tarski, A.: Remarks on projective algebras. In: Bulletin of the american mathematical society, vol. 54, pp. 80\u201381 (1948)","key":"10141_CR17"},{"doi-asserted-by":"crossref","unstructured":"Chu, E., Beckmann, J.L., Naughton, J.F.: The case for a wide-table approach to manage sparse relational data sets. In: C.Y. Chan, B.C. Ooi, A. Zhou (eds.) Proceedings of the ACM SIGMOD international conference on management of data, Beijing, China, June 12-14, 2007, pp. 821\u2013832. ACM (2007)","key":"10141_CR18","DOI":"10.1145\/1247480.1247571"},{"unstructured":"Codd, E.F.: Relational completeness of data base sublanguages. In: Database systems, pp. 65\u201398. Prentice-Hall (1972)","key":"10141_CR19"},{"issue":"1","key":"10141_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00453-007-9089-3","volume":"53","author":"R Cohen","year":"2009","unstructured":"Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., Peleg, D.: Labeling schemes for tree representation. Algorithmica 53(1), 1\u201315 (2009)","journal-title":"Algorithmica"},{"doi-asserted-by":"crossref","unstructured":"Courcelle, B.: The monadic second-order logic of graphs. i. recognizable sets of finite graphs. Inf. Comput. 85(1), 12\u201375 (1990)","key":"10141_CR21","DOI":"10.1016\/0890-5401(90)90043-H"},{"issue":"1","key":"10141_CR22","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/s10878-009-9260-7","volume":"21","author":"B Courcelle","year":"2011","unstructured":"Courcelle, B., Gavoille, C., Kant\u00e9, M.M.: Compact labelings for efficient first-order model-checking. J. Comb. Optim. 21(1), 19\u201346 (2011)","journal-title":"J. Comb. Optim."},{"issue":"1","key":"10141_CR23","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/0022-0000(90)90031-F","volume":"41","author":"R Dechter","year":"1990","unstructured":"Dechter, R.: Decomposing a relation into a tree of binary relations. J. Comput. Syst. Sci. 41(1), 2\u201324 (1990)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"10141_CR24","doi-asserted-by":"publisher","first-page":"453","DOI":"10.1145\/331983.331984","volume":"24","author":"D Dey","year":"1999","unstructured":"Dey, D., Storey, V.C., Barron, T.M.: Improving database design through the analysis of relationships. ACM Trans. Database Syst. 24(4), 453\u2013486 (1999)","journal-title":"ACM Trans. Database Syst."},{"doi-asserted-by":"crossref","unstructured":"Enderton, H.B.: A mathematical introduction to logic, 2 edn. Academic Press (2001)","key":"10141_CR25","DOI":"10.1016\/B978-0-08-049646-7.50005-9"},{"unstructured":"Esperet, L., Harms, N., Zamaraev, V.: Optimal adjacency labels for subgraphs of cartesian products (2022)","key":"10141_CR26"},{"unstructured":"Fagin, R.: Generalized first-order spectra, and polynomial. time recognizable sets. SIAM-AMS Proc. 7, 43\u201373 (1974)","key":"10141_CR27"},{"doi-asserted-by":"crossref","unstructured":"Flajolet, P., Sedgewick, R.: Analytic combinatorics. Cambridge University Press (2009)","key":"10141_CR28","DOI":"10.1017\/CBO9780511801655"},{"unstructured":"Fra\u00efss\u00e9, R.: Theory of relations, studies in logic and the foundations of mathematics, vol. 145. Elsevier (2000)","key":"10141_CR29"},{"doi-asserted-by":"crossref","unstructured":"Gavoille, C., Labourel, A.: Shorter implicit representation for planar graphs and bounded treewidth graphs. In: L. Arge, M. Hoffmann, E. Welzl (eds.) Algorithms - ESA 2007, 15th Annual european symposium, Eilat, Israel, October 8-10, 2007, proceedings, lecture notes in computer science, vol. 4698, pp. 582\u2013593. Springer (2007)","key":"10141_CR30","DOI":"10.1007\/978-3-540-75520-3_52"},{"issue":"2","key":"10141_CR31","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/s00446-002-0073-5","volume":"16","author":"C Gavoille","year":"2003","unstructured":"Gavoille, C., Peleg, D.: Compact and localized distributed data structures. Distrib. Comput. 16(2), 111\u2013120 (2003)","journal-title":"Distrib. Comput."},{"issue":"1","key":"10141_CR32","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/j.jalgor.2004.05.002","volume":"53","author":"C Gavoille","year":"2004","unstructured":"Gavoille, C., Peleg, D., P\u00e9rennes, S., Raz, R.: Distance labeling in graphs. J. Algorithms 53(1), 85\u2013112 (2004)","journal-title":"J. Algorithms"},{"issue":"4","key":"10141_CR33","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1137\/0405049","volume":"5","author":"S Kannan","year":"1992","unstructured":"Kannan, S., Naor, M., Rudich, S.: Implicit representation of graphs. SIAM J. Discrete Math. 5(4), 596\u2013603 (1992)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"10141_CR34","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1145\/319732.319745","volume":"7","author":"W Kim","year":"1982","unstructured":"Kim, W.: On optimizing an sql-like nested query. ACM Trans. Database Syst. 7(3), 443\u2013469 (1982)","journal-title":"ACM Trans. Database Syst."},{"issue":"12","key":"10141_CR35","doi-asserted-by":"publisher","first-page":"1721","DOI":"10.1016\/j.ic.2007.08.004","volume":"205","author":"A Korman","year":"2007","unstructured":"Korman, A., Peleg, D.: Labeling schemes for weighted dynamic trees. Inf. Comput. 205(12), 1721\u20131740 (2007)","journal-title":"Inf. Comput."},{"issue":"2","key":"10141_CR36","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/s00446-008-0061-5","volume":"21","author":"A Korman","year":"2008","unstructured":"Korman, A., Peleg, D.: Compact separator decompositions in dynamic trees and applications to labeling schemes. Distrib Comput. 21(2), 141\u2013161 (2008)","journal-title":"Distrib Comput."},{"issue":"1","key":"10141_CR37","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/s00224-003-1106-6","volume":"37","author":"A Korman","year":"2004","unstructured":"Korman, A., Peleg, D., Rodeh, Y.: Labeling schemes for dynamic tree networks. Theor. Comput. Syst. 37(1), 49\u201375 (2004)","journal-title":"Theor. Comput. Syst."},{"doi-asserted-by":"crossref","unstructured":"Li, M., Vit\u00e1nyi, P.: An introduction to kolmogorov complexity and its applications, 3 edn. Springer-Verlag (2008)","key":"10141_CR38","DOI":"10.1007\/978-0-387-49820-1"},{"doi-asserted-by":"crossref","unstructured":"van Lint, P.H.: Introduction to coding theory, 3rd edition edn. Springer-Verlag (1999)","key":"10141_CR39","DOI":"10.1007\/978-3-642-58575-3"},{"issue":"1","key":"10141_CR40","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1017\/S2040618500035139","volume":"7","author":"J Moon","year":"1965","unstructured":"Moon, J.: On minimal $$n$$-universal graphs. Proc. Glasg. Math. Assoc. 7(1), 32\u201333 (1965)","journal-title":"Proc. Glasg. Math. Assoc."},{"unstructured":"M\u00fcller, J.: Local structure in graph classes. Ph.D. thesis, Georgia Tech (1988)","key":"10141_CR41"},{"doi-asserted-by":"crossref","unstructured":"\u00d6szu, M.T., Valduriez, P.: Principles of distributed database systems, 3rd edition edn. Springer-Verlag (2011)","key":"10141_CR42","DOI":"10.1007\/978-1-4419-8834-8"},{"unstructured":"Petersen, C., Rotbart, N., Simonsen, J.G., Wulff-Nilsen, C.: Near optimal adjacency labeling schemes for power-law graphs. In: I. Chatzigiannakis, M. Mitzenmacher, Y. Rabani, D. Sangiorgi (eds.) 43rd International colloquium on automata, languages, and programming, ICALP 2016, July 11-15, 2016, Rome, Italy, LIPIcs, vol. 55, pp. 133:1\u2013133:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2016)","key":"10141_CR43"},{"doi-asserted-by":"crossref","unstructured":"Ross, K.A., Stoyanovich, J.: Symmetric relations and cardinality-bounded multisets in database systems. In: Proceedings of the 38th International conference on very large data bases - vol. 30, VLDB \u201904, pp. 912\u2013923. VLDB Endowment (2004)","key":"10141_CR44","DOI":"10.1016\/B978-012088469-8.50080-2"},{"issue":"6","key":"10141_CR45","doi-asserted-by":"publisher","first-page":"993","DOI":"10.1145\/1039488.1039493","volume":"51","author":"M Thorup","year":"2004","unstructured":"Thorup, M.: Compact oracles for reachability and approximate distances in planar digraphs. J. ACM 51(6), 993\u20131024 (2004)","journal-title":"J. ACM"},{"unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: Proceedings of the 13th Annual ACM Symposium on parallel algorithms and architectures, SPAA 2001, Heraklion, Crete Island, Greece, July 4-6, 2001, pp. 1\u201310 (2001)","key":"10141_CR46"},{"issue":"14","key":"10141_CR47","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1016\/j.ipl.2011.04.006","volume":"111","author":"O Weimann","year":"2011","unstructured":"Weimann, O., Peleg, D.: A note on exact distance labeling. Inf. Process. Lett. 111(14), 671\u2013673 (2011)","journal-title":"Inf. Process. Lett."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-023-10141-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-023-10141-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-023-10141-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T01:03:22Z","timestamp":1701997402000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-023-10141-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,15]]},"references-count":47,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["10141"],"URL":"https:\/\/doi.org\/10.1007\/s00224-023-10141-z","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2023,8,15]]},"assertion":[{"value":"3 July 2023","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 August 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}