{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T01:40:06Z","timestamp":1704073206331},"reference-count":39,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[2001,2,1]],"date-time":"2001-02-01T00:00:00Z","timestamp":980985600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":4549,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2001,2]]},"DOI":"10.1016\/s0166-218x(00)00225-0","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T18:17:26Z","timestamp":1027621046000},"page":"193-210","source":"Crossref","is-referenced-by-count":10,"title":["Representing graphs implicitly using almost optimal space"],"prefix":"10.1016","volume":"108","author":[{"given":"Maurizio","family":"Talamo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paola","family":"Vocca","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0166-218X(00)00225-0_BIB1","series-title":"Design and Analysis of Computer Algorithms","author":"Aho","year":"1974"},{"issue":"1","key":"10.1016\/S0166-218X(00)00225-0_BIB2","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0004-3702(96)00014-8","article-title":"The complexity of searching implicit graphs","volume":"86","author":"Balc\u00e1zar","year":"1996","journal-title":"Artificial Intelligence"},{"issue":"3","key":"10.1016\/S0166-218X(00)00225-0_BIB3","first-page":"113","article-title":"The complexity of algorithmic problems on succint instances","volume":"2","author":"Balc\u00e1zar","year":"1992","journal-title":"Algorith. Rev."},{"key":"10.1016\/S0166-218X(00)00225-0_BIB4","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1109\/TIT.1966.1053860","article-title":"Coding vertices of a graph","volume":"12","author":"Breuer","year":"1966","journal-title":"IEEE Trans. Inform. Theory"},{"key":"10.1016\/S0166-218X(00)00225-0_BIB5","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1016\/0022-247X(67)90082-0","article-title":"An unexpected result on coding vertices","volume":"20","author":"Breuer","year":"1967","journal-title":"J. Math. Anal. Appl."},{"key":"10.1016\/S0166-218X(00)00225-0_BIB6","doi-asserted-by":"crossref","unstructured":"H. Buhrman, J.H. Hoepman, Paul Vit\u00e1nyi, Optimal routing tables, in: Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing (PODC \u201996), New York, USA, May 1996, ACM, pp. 134\u2013142.","DOI":"10.1145\/248052.248076"},{"key":"10.1016\/S0166-218X(00)00225-0_BIB7","doi-asserted-by":"crossref","unstructured":"A. Fiat, M. Naor, Implicit O(1) probe search, in Proceedings of the 21st Annual ACM Symposium on Theory of Computing, Seattle, Washington, DC, 1989, pp. 336\u2013344.","DOI":"10.1145\/73007.73039"},{"key":"10.1016\/S0166-218X(00)00225-0_BIB8","doi-asserted-by":"crossref","unstructured":"A. Fiat, M. Naor, J.P. Schmidt, A. Siegel, Non-oblivious hashing, in: Proceedings of the 20th Annual ACM Symposium on Theory of Computing: Chicago, Illinois, May 2\u20134, 1988, New York, NY 10036, USA, 1988. ACM Press, pp. 367\u2013376.","DOI":"10.1145\/62212.62248"},{"key":"10.1016\/S0166-218X(00)00225-0_BIB9","doi-asserted-by":"crossref","unstructured":"P. Fraigniaud, C. Gavoille, Local memory requirement of universal routing schemes, in: Proceedings of the Eighth Annual ACM Symposium on Parallel Algorithms and Architectures, Padua, Italy, June 24\u201326, 1996. SIGACT\/SIGARCH, pp. 183\u2013188.","DOI":"10.1145\/237502.237541"},{"issue":"1","key":"10.1016\/S0166-218X(00)00225-0_BIB10","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1145\/322358.322364","article-title":"Implicit data structures for the dictionary problem","volume":"30","author":"Frederickson","year":"1980","journal-title":"J. ACM"},{"key":"10.1016\/S0166-218X(00)00225-0_BIB11","doi-asserted-by":"crossref","unstructured":"G.N. Frederickson, R. Janardan, Optimal message routing without complete routing tables (preliminary version), in: Proceedings of the Fifth Annual ACM Symposium on Principles of Distributed Computing, Calgary, Alberta, Canada, 11\u201313 August 1986, pp. 88\u201397.","DOI":"10.1145\/10590.10598"},{"key":"10.1016\/S0166-218X(00)00225-0_BIB12","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/BF01762113","article-title":"Designing networks with compact routing tables","volume":"3","author":"Frederickson","year":"1988","journal-title":"Algorithmica"},{"key":"10.1016\/S0166-218X(00)00225-0_BIB13","doi-asserted-by":"crossref","first-page":"843","DOI":"10.1137\/0218058","article-title":"Efficient message routing in planar networks","volume":"18","author":"Frederickson","year":"1989","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0166-218X(00)00225-0_BIB14","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1137\/0219011","article-title":"Space efficient message routing in c-decomposable networks","volume":"19","author":"Frederickson","year":"1990","journal-title":"SIAM J. Comput."},{"issue":"3","key":"10.1016\/S0166-218X(00)00225-0_BIB15","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1145\/828.1884","article-title":"Storing a sparse table with O(1) worst case access time","volume":"31","author":"Fredman","year":"1984","journal-title":"J. Assoc. Comput. Machin."},{"issue":"3","key":"10.1016\/S0166-218X(00)00225-0_BIB16","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/S0019-9958(83)80004-7","article-title":"Succinct representations of graphs","volume":"56","author":"Galperin","year":"1983","journal-title":"Inf. Control"},{"key":"10.1016\/S0166-218X(00)00225-0_BIB17","series-title":"Distributed Algorithms-WDAG\u201996","first-page":"206","article-title":"Topological routing","volume":"1151","author":"Gambosi","year":"1996"},{"key":"10.1016\/S0166-218X(00)00225-0_BIB18","doi-asserted-by":"crossref","unstructured":"C. Gavoille, S. P\u00e9renn\u00e8s, Memory requirement for routing in distributed networks (extended abstract), in: Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing (PODC \u201996), New York, USA, May 1996. ACM pp. 125\u2013133.","DOI":"10.1145\/248052.248075"},{"key":"10.1016\/S0166-218X(00)00225-0_BIB19","series-title":"Graph Theory","author":"Harary","year":"1972"},{"key":"10.1016\/S0166-218X(00)00225-0_BIB20","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/BF00288971","article-title":"Representation of graphs","volume":"17","author":"Itai","year":"1982","journal-title":"Acta Informatica"},{"key":"10.1016\/S0166-218X(00)00225-0_BIB21","doi-asserted-by":"crossref","unstructured":"S. Kannan, M. Naor, S. Rudich, Implicit representation of graphs, SIAM J. Discrete Math. 5(4) (1992) 596\u2013603.","DOI":"10.1137\/0405049"},{"key":"10.1016\/S0166-218X(00)00225-0_BIB22","doi-asserted-by":"crossref","unstructured":"M. Li, P. Vitanyi, An Introduction to Kolmogorov Complexity and its Applications, 2nd Edition, Springer, Berlin, 1997.","DOI":"10.1007\/978-1-4757-2606-0"},{"key":"10.1016\/S0166-218X(00)00225-0_BIB23","doi-asserted-by":"crossref","unstructured":"J. Balc\u00e1zar, A. Lozano, The complexity of graph problems for succinctly represented graphs, in: Graph-Theoretic Concepts in Computer Science, Berlin, June 1990, Springer, Berlin, pp. 277\u2013286.","DOI":"10.1007\/3-540-52292-1_20"},{"issue":"1","key":"10.1016\/S0166-218X(00)00225-0_BIB24","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1016\/0022-0000(86)90043-7","article-title":"An implicit data structure supporting insertion, deletion, search in O(log2 n) time","volume":"33","author":"Munro","year":"1986","journal-title":"J. Comput. System Sci."},{"key":"10.1016\/S0166-218X(00)00225-0_BIB25","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1016\/0022-0000(80)90037-9","article-title":"Implicit data structures for fast search and update","volume":"21","author":"Munro","year":"1980","journal-title":"J. Comp. Syst. Sci."},{"issue":"6","key":"10.1016\/S0166-218X(00)00225-0_BIB26","doi-asserted-by":"crossref","first-page":"1259","DOI":"10.1137\/S0097539793254571","article-title":"What can be computed locally?","volume":"24","author":"Naor","year":"1995","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0166-218X(00)00225-0_BIB27","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/0020-0190(88)90058-0","article-title":"Implicit data structure for linear hashing schemes","volume":"29","author":"Ouksel","year":"1988","journal-title":"Inform. Proc. Lett."},{"issue":"3","key":"10.1016\/S0166-218X(00)00225-0_BIB28","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1016\/S0019-9958(86)80009-2","article-title":"A note on succinct representations of graphs","volume":"71","author":"Papadimitriou","year":"1986","journal-title":"Inform. Control"},{"issue":"3","key":"10.1016\/S0166-218X(00)00225-0_BIB29","doi-asserted-by":"crossref","first-page":"510","DOI":"10.1145\/65950.65953","article-title":"A trade-off between space and efficiency for routing tables","volume":"36","author":"Peleg","year":"1989","journal-title":"J. ACM, JACM"},{"issue":"1","key":"10.1016\/S0166-218X(00)00225-0_BIB30","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1093\/comjnl\/28.1.5","article-title":"Labelling and implicit routing in networks","volume":"28","author":"Santoro","year":"1985","journal-title":"Comput. J."},{"key":"10.1016\/S0166-218X(00)00225-0_BIB31","series-title":"Proceedings of 24th International Workshop on Graph\u2013Theoretic Concepts in Computer Science WG\u201998","first-page":"164","article-title":"Compact implicit representation of graphs","volume":"1517","author":"Talamo","year":"1998"},{"key":"10.1016\/S0166-218X(00)00225-0_BIB32","unstructured":"M. Talamo, P. Vocca, An efficient data structure for lattices operations, SIAM J. Comp. (1998) to be published."},{"issue":"2","key":"10.1016\/S0166-218X(00)00225-0_BIB33","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1016\/S0304-3975(96)00209-5","article-title":"A data structure for lattice representation","volume":"175","author":"Talamo","year":"1997","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0166-218X(00)00225-0_BIB34","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1016\/0166-218X(84)90126-4","article-title":"Succint representation of graphs","volume":"8","author":"Turan","year":"1984","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0166-218X(00)00225-0_BIB35","series-title":"Handbook of Theoretical Computer Science, Vol. A","first-page":"525","article-title":"Graph algorithms","author":"van Leeuwen","year":"1990"},{"key":"10.1016\/S0166-218X(00)00225-0_BIB36","series-title":"The Book of L, Vol. 790","article-title":"Computer networks with compact routing tables","author":"van Leeuwen","year":"1986"},{"key":"10.1016\/S0166-218X(00)00225-0_BIB37","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1093\/comjnl\/30.4.298","article-title":"Interval routing","volume":"30","author":"van Leeuwen","year":"1987","journal-title":"Comput. J."},{"key":"10.1016\/S0166-218X(00)00225-0_BIB38","doi-asserted-by":"crossref","unstructured":"J. van Leeuwen, R.B. Tan, Compact routing methods: a survey, in: Proceedings of the Colloquium on Structural Information and Communication Complexity (SICC\u201994). Carleton University Press, 1994.","DOI":"10.1515\/9780773591158-007"},{"issue":"6","key":"10.1016\/S0166-218X(00)00225-0_BIB39","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1007\/BF01185207","article-title":"Algorithms for parallel memory, I: two-level memories","volume":"12","author":"Vitter","year":"1994","journal-title":"Algorithmica"}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X00002250?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X00002250?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T01:01:33Z","timestamp":1704070893000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X00002250"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,2]]},"references-count":39,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2001,2]]}},"alternative-id":["S0166218X00002250"],"URL":"https:\/\/doi.org\/10.1016\/s0166-218x(00)00225-0","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[2001,2]]}}}