{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:45:38Z","timestamp":1781077538864,"version":"3.54.1"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540424932","type":"print"},{"value":"9783540446767","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44676-1_40","type":"book-chapter","created":{"date-parts":[[2007,5,18]],"date-time":"2007-05-18T12:43:15Z","timestamp":1179492195000},"page":"476-487","source":"Crossref","is-referenced-by-count":45,"title":["Approximate Distance Labeling Schemes"],"prefix":"10.1007","author":[{"given":"Cyril","family":"Gavoille","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michal","family":"Katz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nir A.","family":"Katz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christophe","family":"Paul","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2001,8,17]]},"reference":[{"key":"40_CR1","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1016\/0022-247X(67)90082-0","volume":"20","author":"M. A. Breuer","year":"1967","unstructured":"M. A. Breuer and J. Folkman. An unexpected result on coding the vertices of a graph. J. of Mathematical Analysis and Applications, 20:583\u2013600, 1967.","journal-title":"J. of Mathematical Analysis and Applications"},{"key":"40_CR2","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1109\/TIT.1966.1053860","volume":"IT-12","author":"M. A. Breuer","year":"1966","unstructured":"M. A. Breuer. Coding the vertexes of a graph. IEEE Trans. on Information Theory, IT-12:148\u2013153, 1966.","journal-title":"IEEE Trans. on Information Theory"},{"issue":"3","key":"40_CR3","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1137\/S0895480193250125","volume":"10","author":"D. G. Corneil","year":"1997","unstructured":"D. G. Corneil, S. Olariu, and L. Stewart. Asteroidal triple-free graphs. SIAM Journal on Discrete Mathematics, 10(3):399\u2013430, Aug. 1997.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"40_CR4","first-page":"215","volume":"1","author":"P. Erd\u00f6s","year":"1966","unstructured":"P. Erd\u00f6s, A. R\u00e9nyi, and V. T. S\u00f3s. On a problem of graph theory. In Studia Sci. Math. Hungar., vol. 1, pp. 215\u2013235, 1966.","journal-title":"Studia Sci. Math. Hungar."},{"issue":"4","key":"40_CR5","doi-asserted-by":"crossref","first-page":"843","DOI":"10.1137\/0218058","volume":"18","author":"G. N. Frederickson","year":"1989","unstructured":"G. N. Frederickson and R. Janardan. Efficient message routing in planar networks. SIAM Journal on Computing, 18(4):843\u2013857, Aug. 1989.","journal-title":"SIAM Journal on Computing"},{"key":"40_CR6","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/0022-0000(93)90040-4","volume":"47","author":"M. L. Fredman","year":"1993","unstructured":"M. L. Fredman and D. E. Willard. Surpassing the information theoric bound with fusion trees. J. of Computer and System Sciences, 47:424\u2013436, 1993.","journal-title":"J. of Computer and System Sciences"},{"key":"40_CR7","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M. C. Golumbic","year":"1980","unstructured":"M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs. Academic Press, Harcourt Brace Jovanovich, Academic Press edition, 1980."},{"key":"40_CR8","doi-asserted-by":"crossref","unstructured":"R. L. Graham and H. O. Pollak. On embedding graphs in squashed cubes. Lecture Notes in Mathematics, 303:99\u2013110, 1972.","DOI":"10.1007\/BFb0067362"},{"key":"40_CR9","volume-title":"TR RR-1250-00","author":"C. Gavoille","year":"2000","unstructured":"C. Gavoille, M. Katz, N. A. Katz, C. Paul, and D. Peleg. Approximate distance labeling schemes. TR RR-1250-00, LaBRI, University of Bordeaux, 351, cours de la Lib\u00e9ration, 33405 Talence Cedex, France, Dec. 2000."},{"key":"40_CR10","unstructured":"C. Gavoille, D. Peleg, S. P\u00e9rennes, and R. Raz. Distance labeling in graphs. In 12 th Symposium on Discrete Algorithms (SODA), pp. 210\u2013219. ACM-SIAM, Jan. 2001."},{"key":"40_CR11","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"516","DOI":"10.1007\/3-540-46541-3_43","volume-title":"17th Annual Symposium on Theoretical Aspects of Computer Science (STACS)","author":"M. Katz","year":"2000","unstructured":"M. Katz, N. A. Katz, and D. Peleg. Distance labeling schemes for well-separated graph classes. In 17 th Annual Symposium on Theoretical Aspects of Computer Science (STACS), vol. 1770 of LNCS, pp. 516\u2013528. Springer, Feb. 2000."},{"key":"40_CR12","doi-asserted-by":"crossref","unstructured":"S. Kannan, M. Naor, and S. Rudich. Implicit representation of graphs. In 20 th Annual ACM Symposium on Theory of Computing (STOC), pp. 334\u2013343, Chicago, IL, May 1988.","DOI":"10.1145\/62212.62244"},{"key":"40_CR13","doi-asserted-by":"crossref","first-page":"45","DOI":"10.4064\/fm-51-1-45-64","volume":"51","author":"C. G. Lekkerkerker","year":"1962","unstructured":"C. G. Lekkerkerker and J. Ch. Boland. Representation of a finite graph by a set of intervals on the real line. Fund. Math., 51:45\u201364, 1962.","journal-title":"Fund. Math."},{"issue":"1","key":"40_CR14","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1090\/S0273-0979-1995-00569-0","volume":"32","author":"F. Lazebnik","year":"1995","unstructured":"F. Lazebnik, V. A. Ustimenko, and A. J. Woldar. A new series of dense graphs of high girth. Bulletin of American Mathematical Society (New Series), 32(1):73\u201379, 1995.","journal-title":"Bulletin of American Mathematical Society (New Series)"},{"key":"40_CR15","doi-asserted-by":"crossref","unstructured":"J. I. Munro and V. Raman. Succinct representation of balanced parentheses, static trees and planar graphs. In 38th Symposium on Foundations of Computer Science (FOCS), pp. 118\u2013126. IEEE Comp. Society Press, 1997.","DOI":"10.1109\/SFCS.1997.646100"},{"key":"40_CR16","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/3-540-62034-6_35","volume-title":"16th FST&TCS","author":"J. I. Munro","year":"1996","unstructured":"J. I. Munro. Tables. In 16th FST&TCS, vol. 1180 of LNCS, pp. 37\u201342. Springer-Verlag, 1996."},{"key":"40_CR17","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1007\/3-540-46784-X_5","volume-title":"25th International Workshop, Graph-Theoretic Concepts in Computer Science (WG)","author":"D. Peleg","year":"1999","unstructured":"D. Peleg. Proximity-preserving labeling schemes and their applications. In 25th International Workshop, Graph-Theoretic Concepts in Computer Science (WG), vol. 1665 of LNCS, pp. 30\u201341. Springer, June 1999."},{"key":"40_CR18","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"N. Robertson and P. D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms, 7:309\u2013322, 1986.","journal-title":"Journal of Algorithms"},{"issue":"1","key":"40_CR19","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/BF02579350","volume":"3","author":"P. Winkler","year":"1983","unstructured":"P. Winkler. Proof of the squashed cube conjecture. Combinatorica, 3(1):135\u2013139, 1983.","journal-title":"Combinatorica"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44676-1_40","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T00:44:08Z","timestamp":1556412248000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44676-1_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424932","9783540446767"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-44676-1_40","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2001]]}}}