{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,24]],"date-time":"2025-02-24T05:14:49Z","timestamp":1740374089012,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540200642"},{"type":"electronic","value":"9783540396581"}],"license":[{"start":{"date-parts":[[2003,1,1]],"date-time":"2003-01-01T00:00:00Z","timestamp":1041379200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-39658-1_25","type":"book-chapter","created":{"date-parts":[[2010,7,22]],"date-time":"2010-07-22T23:24:30Z","timestamp":1279841070000},"page":"254-265","source":"Crossref","is-referenced-by-count":8,"title":["Optimal Distance Labeling for Interval and Circular-Arc Graphs"],"prefix":"10.1007","author":[{"given":"Cyril","family":"Gavoille","sequence":"first","affiliation":[]},{"given":"Christophe","family":"Paul","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"25_CR1","unstructured":"Abiteboul, S., Kaplan, H., Milo, T.: Compact labeling schemes for ancestor queries. In: 12th Symp. on Discrete Algorithms (SODA), pp. 547\u2013556 (2001)"},{"key":"25_CR2","unstructured":"Alstrup, S., Bille, P., Rauhe, T.: Labeling schemes for small distances in trees. In: 15th Symp. on Discrete Algorithms, (SODA) (2003)"},{"key":"25_CR3","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Gavoille, C., Kaplan, H., Rauhe, T.: Nearest common ancestors: A survey and a new distributed algorithm. In: 14th ACM Symp. on Parallel Algorithms and Architecture (SPAA), August 2002, pp. 258\u2013264 (2002)","DOI":"10.1145\/564870.564914"},{"key":"25_CR4","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Rauhe, T.: Small induced-universal graphs and compact implicit graph representations. In: 43rd IEEE Symp. on Foundations of Computer Science (FOCS), pp. 53\u201362 (2002)","DOI":"10.1109\/SFCS.2002.1181882"},{"key":"25_CR5","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1016\/S0022-0000(05)80002-9","volume":"48","author":"O. Berkman","year":"1994","unstructured":"Berkman, O., Vishkin, U.: Finding level-ancestors in trees. J. of Computer and System Sciences\u00a048, 214\u2013230 (1994)","journal-title":"J. of Computer and System Sciences"},{"key":"25_CR6","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1002\/(SICI)1097-0037(199807)31:4<249::AID-NET5>3.0.CO;2-D","volume":"31","author":"D.Z. Chen","year":"1998","unstructured":"Chen, D.Z., Lee, D., Sridhar, R., Sekharan, C.N.: Solving the all-pair shortest path query problem on interval and circular-arc graphs. Networks\u00a031, 249\u2013257 (1998)","journal-title":"Networks"},{"key":"25_CR7","doi-asserted-by":"crossref","unstructured":"Cohen, J.E., Koml\u00f3s, J., Mueller, T.: The probability of an interval graph, and why it matters. In: Proc. of Symposia in Pure Mathematics, vol.\u00a034, pp. 97\u2013115 (1979)","DOI":"10.1090\/pspum\/034\/525322"},{"key":"25_CR8","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0020-0190(95)00046-F","volume":"55","author":"D. Corneil","year":"1995","unstructured":"Corneil, D., Kim, H., Natarajan, S., Olariu, S., Sprague, A.: Simple linear time algorithm of unit interval graphs. Info. Proces. Letters\u00a055, 99\u2013104 (1995)","journal-title":"Info. Proces. Letters"},{"key":"25_CR9","unstructured":"Courcelle, B., Vanicat, R.: Query efficient implementation of graphs of bounded clique width. Discrete Applied Mathematics (2001) (to appear)"},{"key":"25_CR10","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/0020-0190(95)00133-W","volume":"56","author":"C. Figueiredo Herrera de","year":"1995","unstructured":"de Figueiredo Herrera, C., Meidanis, J., de Mello, C.P.: A lineartime algorithm for proper interval recognition. Information Processing Letters\u00a056, 179\u2013184 (1995)","journal-title":"Information Processing Letters"},{"key":"25_CR11","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1145\/568438.568451","volume":"32","author":"C. Gavoille","year":"2001","unstructured":"Gavoille, C.: Routing in distributed networks: Overview and open problems. ACM SIGACT News - Distributed Computing Column\u00a032, 36\u201352 (2001)","journal-title":"ACM SIGACT News - Distributed Computing Column"},{"key":"25_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"476","DOI":"10.1007\/3-540-44676-1_40","volume-title":"Algorithms - ESA 2001","author":"C. Gavoille","year":"2001","unstructured":"Gavoille, C., Katz, M., Katz, N.A., Paul, C., Peleg, D.: Approximate distance labeling schemes. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol.\u00a02161, pp. 476\u2013488. Springer, Heidelberg (2001)"},{"key":"25_CR13","doi-asserted-by":"crossref","unstructured":"Gavoille, C., Paul, C.: Distance labeling scheme and split decomposition. Discrete Mathematics (2003) (to appear)","DOI":"10.1016\/S0012-365X(03)00232-2"},{"key":"25_CR14","unstructured":"Gavoille, C., Peleg, D.: Compact and localized distributed data structures, Research Report RR-1261-01, LaBRI, University of Bordeaux (August 2001); To appear in J. of Distributed Computing for the PODC 20-Year Special Issue"},{"key":"25_CR15","unstructured":"Gavoille, C., Peleg, D., P\u00e9rennes, S., Raz, R.: Distance labeling in graphs. In: 12th Symp. on Discrete Algorithms (SODA), pp. 210\u2013219 (2001)"},{"key":"25_CR16","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1090\/S0002-9947-1982-0662044-8","volume":"272","author":"P. Hanlon","year":"1982","unstructured":"Hanlon, P.: Counting interval graphs. Transactions of the American Mathematical Society\u00a0272, 383\u2013426 (1982)","journal-title":"Transactions of the American Mathematical Society"},{"key":"25_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/3-540-52921-7_59","volume-title":"Algorithms","author":"P. Hell","year":"1990","unstructured":"Hell, P., Bang-Jensen, J., Huang, J.: Local tournaments and proper circular arc graphs. In: Asano, T., Imai, H., Ibaraki, T., Nishizeki, T. (eds.) SIGAL 1990. LNCS, vol.\u00a0450, pp. 101\u2013108. Springer, Heidelberg (1990)"},{"key":"25_CR18","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. on Discrete Mathematics\u00a05, 596\u2013603 (1992)","journal-title":"SIAM J. on Discrete Mathematics"},{"key":"25_CR19","unstructured":"Kaplan, H., Milo, T., Shabo, R.: A comparison of labeling schemes for ancestor queries. In: 14th Symp. on Discrete Algorithms (SODA) (2002)"},{"key":"25_CR20","unstructured":"Katz, M., Katz, N.A., Korman, A., Peleg, D.: Labeling schemes for flow and connectivity. In: 13th Symp. on Discrete Algorithms (SODA), pp. 927\u2013936 (2002)"},{"key":"25_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"516","DOI":"10.1007\/3-540-46541-3_43","volume-title":"STACS 2000","author":"M. Katz","year":"2000","unstructured":"Katz, M., Katz, N.A., Peleg, D.: Distance labeling schemes for wellseparated graph classes. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol.\u00a01770, pp. 516\u2013528. Springer, Heidelberg (2000)"},{"key":"25_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/3-540-45841-7_5","volume-title":"STACS 2002","author":"A. Korman","year":"2002","unstructured":"Korman, A., Peleg, D., Rodeh, Y.: Labeling schemes for dynamic tree networks. In: Alt, H., Ferreira, A. (eds.) STACS 2002. LNCS, vol.\u00a02285, pp. 76\u201387. Springer, Heidelberg (2002)"},{"key":"25_CR23","doi-asserted-by":"crossref","unstructured":"McConnell, R.M.: Linear-time recognition of circular-arc graphs. In: 42th IEEE Symp. on Foundations of Computer Science (FOCS) (2001)","DOI":"10.1109\/SFCS.2001.959913"},{"key":"25_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1007\/3-540-44612-5_53","volume-title":"Mathematical Foundations of Computer Science 2000","author":"D. Peleg","year":"2000","unstructured":"Peleg, D.: Informative labeling schemes for graphs. In: Nielsen, M., Rovan, B. (eds.) MFCS 2000. LNCS, vol.\u00a01893, pp. 579\u2013588. Springer, Heidelberg (2000)"},{"key":"25_CR25","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Proximity-preserving labeling schemes. J. of Graph Theory\u00a033 (2000)","DOI":"10.1002\/(SICI)1097-0118(200003)33:3<167::AID-JGT7>3.0.CO;2-5"},{"key":"25_CR26","first-page":"139","volume-title":"Proof Techniques in Graph Theory","author":"F. Roberts","year":"1969","unstructured":"Roberts, F.: Indifference graphs. In: Proof Techniques in Graph Theory, pp. 139\u2013146. Academic Press, London (1969)"},{"key":"25_CR27","doi-asserted-by":"crossref","unstructured":"Thorup, M.: Compact oracles for reachability and approximate distances in planar digraphs. In: 42th IEEE Symp. on Foundations of Computer Science (FOCS) (2001)","DOI":"10.1109\/SFCS.2001.959898"},{"key":"25_CR28","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. In: 33rd ACM Symp. on Theory of Computing (STOC), pp. 183\u2013192 (2001)","DOI":"10.1145\/380752.380798"},{"key":"25_CR29","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: 13th ACM Symp. on Parallel Algorithms and Architectures (SPAA), pp. 1\u201310 (2001)","DOI":"10.1145\/378580.378581"},{"key":"25_CR30","unstructured":"Wegner, G.: Eigenschaften der Neuen homologish-einfacher Familien im Rn, PhD thesis, University of G\u00f6ttingen (1967)"}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2003"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-39658-1_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,23]],"date-time":"2025-02-23T07:38:06Z","timestamp":1740296286000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-39658-1_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540200642","9783540396581"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-39658-1_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}