{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T21:56:39Z","timestamp":1725573399501},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540309352"},{"type":"electronic","value":"9783540324263"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11602613_111","type":"book-chapter","created":{"date-parts":[[2005,12,2]],"date-time":"2005-12-02T08:24:24Z","timestamp":1133511864000},"page":"1122-1131","source":"Crossref","is-referenced-by-count":6,"title":["Localized and Compact Data-Structure for Comparability Graphs"],"prefix":"10.1007","author":[{"given":"Fabrice","family":"Bazzaro","sequence":"first","affiliation":[]},{"given":"Cyril","family":"Gavoille","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"111_CR1","unstructured":"Alstrup, S., Bille, P., Rauhe, T.: Labeling schemes for small distances in trees. In: 14th Symp. on Disc. Algorithms (SODA), pp. 689\u2013698. ACM-SIAM (2003)"},{"key":"111_CR2","doi-asserted-by":"crossref","unstructured":"Atallah, M., Chen, D., Lee, D.: An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications. Algorithm\u00a014 (1995)","DOI":"10.1007\/BF01192049"},{"key":"111_CR3","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1002\/net.3230020103","volume":"2","author":"K.A. Baker","year":"1971","unstructured":"Baker, K.A., Fishburn, P.C., Roberts, F.S.: Partial orders of dimension 2. Networks\u00a02, 11\u201328 (1971)","journal-title":"Networks"},{"key":"111_CR4","doi-asserted-by":"crossref","unstructured":"Bazzaro, F., Gavoille, C.: Localized and compact data-structure for comparability graphs, RR-1343-05, LaBRI, University of Bordeaux\u00a01 (February 2005)","DOI":"10.1007\/11602613_111"},{"key":"111_CR5","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes \u2013 A survey, Philadelphia. SIAM Monographs on Discrete Mathematics and Applications (1999)","DOI":"10.1137\/1.9780898719796"},{"key":"111_CR6","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1007\/s004530010016","volume":"27","author":"S. Chaudhuri","year":"2000","unstructured":"Chaudhuri, S., Zaroliagis, C.D.: Shortest paths in digraphs of small treewidth. Part I: Sequential algorithms. Algorithmica\u00a027, 212\u2013226 (2000)","journal-title":"Algorithmica"},{"key":"111_CR7","doi-asserted-by":"crossref","unstructured":"Chen, D., Lee, D., Sridhar, R., Sekharan, C.: Solving the all-pair shortest path query problem on interval and circular-arc graphs. Networks\u00a031 (1998)","DOI":"10.1002\/(SICI)1097-0037(199807)31:4<249::AID-NET5>3.0.CO;2-D"},{"key":"111_CR8","doi-asserted-by":"crossref","unstructured":"Chepoi, V.D., Dragan, F.F., Vaxes, Y.: Distance and routing labeling schemes for non-positively curved plane graphs. J. of Alghoritms (2005)","DOI":"10.1016\/j.jalgor.2004.07.011"},{"key":"111_CR9","doi-asserted-by":"crossref","unstructured":"Corneil, D.G., Kim, H., Natarajan, S., Olariu, S., Sprague, A.P.: Simple linear time algorithm of unit interval graphs. Inf. Proc. Letters\u00a055 (1995)","DOI":"10.1016\/0020-0190(95)00046-F"},{"key":"111_CR10","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1137\/S0895480193250125","volume":"10","author":"D.G. Corneil","year":"1997","unstructured":"Corneil, D.G., Olariu, S., Stewart, L.: Asteroidal triple-free graphs. SIAM Journal on Discrete Mathematics\u00a010, 399\u2013430 (1997)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"111_CR11","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/S0166-218X(02)00421-3","volume":"131","author":"B. Courcelle","year":"2003","unstructured":"Courcelle, B., Vanicat, R.: Query efficient implementation of graphs of bounded clique-width. Discrete Applied Mathematics\u00a0131, 129\u2013150 (2003)","journal-title":"Discrete Applied Mathematics"},{"key":"111_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/3-540-62559-3_14","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"H.N. Djidjev","year":"1997","unstructured":"Djidjev, H.N.: Efficient algorithms for shortest path queries in planar digraphs. In: D\u2019Amore, F., Marchetti-Spaccamela, A., Franciosa, P.G. (eds.) WG 1996. LNCS, vol.\u00a01197, pp. 151\u2013165. Springer, Heidelberg (1997)"},{"key":"111_CR13","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1137\/S0097539797327908","volume":"29","author":"D. Dor","year":"2000","unstructured":"Dor, D., Halperin, S., Zwick, U.: All-pairs almost shortest paths. SIAM Journal on Computing\u00a029, 1740\u20131759 (2000)","journal-title":"SIAM Journal on Computing"},{"key":"111_CR14","unstructured":"Dragan, F.F., Lomonosov, I.: New routing schemes for interval graphs, circular-arc graphs, and permutation graphs. In: 14 th PDCS, November 2002, pp. 78\u201383 (2002)"},{"key":"111_CR15","doi-asserted-by":"publisher","first-page":"600","DOI":"10.2307\/2371374","volume":"63","author":"B. Dushnik","year":"1941","unstructured":"Dushnik, B., Miller, E.W.: Partially ordered sets. American Journal of Mathematics\u00a063, 600\u2013610 (1941)","journal-title":"American Journal of Mathematics"},{"key":"111_CR16","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":"111_CR17","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/S0012-365X(03)00232-2","volume":"273","author":"C. Gavoille","year":"2003","unstructured":"Gavoille, C., Paul, C.: Distance labeling scheme and split decomposition. Discrete Mathematics\u00a0273, 115\u2013130 (2003)","journal-title":"Discrete Mathematics"},{"key":"111_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/978-3-540-39658-1_25","volume-title":"Algorithms - ESA 2003","author":"C. Gavoille","year":"2003","unstructured":"Gavoille, C., Paul, C.: Optimal distance labeling schemes for interval and circular-arc graphs. In: Di Battista, G., Zwick, U. (eds.) ESA 2003. LNCS, vol.\u00a02832, pp. 254\u2013265. Springer, Heidelberg (2003)"},{"key":"111_CR19","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. J. of Distributed Computing\u00a016, 111\u2013120 (2003); PODC 20-Year Special Issue","journal-title":"J. of Distributed Computing"},{"key":"111_CR20","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\u00e9renn\u00e8s, S., Raz, R.: Distance labeling in graphs. Journal of Algorithms\u00a053, 85\u2013112 (2004)","journal-title":"Journal of Algorithms"},{"key":"111_CR21","doi-asserted-by":"crossref","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. In: Academic Press (ed.) Academic Press, Harcourt Brace Jovanovich (1980)","DOI":"10.1016\/B978-0-12-289260-8.50010-8"},{"key":"111_CR22","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/0020-0190(95)00133-W","volume":"56","author":"C.M. Herrera de Figueiredo","year":"1995","unstructured":"Herrera de Figueiredo, C.M., Meidanis, J.A., Picinin de Mello, C.: A linear-time algorithm for proper interval recognition. Information Processing Letters\u00a056, 179\u2013184 (1995)","journal-title":"Information Processing Letters"},{"key":"111_CR23","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 Journal on Discrete Mathematics\u00a05, 596\u2013603 (1992)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"111_CR24","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., Peleg, D.: Distance labeling schemes for well-separated graph classes. In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol.\u00a01770, pp. 516\u2013528. Springer, Heidelberg (2000)"},{"key":"111_CR25","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1006\/jcss.1997.1493","volume":"55","author":"P.N. Klein","year":"1997","unstructured":"Klein, P.N., Rao, S., Henzinger, M.R., Subramanian, S.: Faster shortest-path algorithms for planar graphs. J. of Comp. and Sys. Sci.\u00a055, 3\u201323 (1997)","journal-title":"J. of Comp. and Sys. Sci."},{"key":"111_CR26","unstructured":"McConnell, R.M., Spinrad, J.P.: Linear-time transitive orientation. In: 8th Symp. on Discrete Algorithms (SODA), January 1997, pp. 19\u201325. ACM-SIAM (1997)"},{"key":"111_CR27","doi-asserted-by":"crossref","unstructured":"McKee, T.A., McMorris, F.R.: Topics in Intersection Graph Theory. SIAM Monographs on Discrete Mathematics and Applications (1999)","DOI":"10.1137\/1.9780898719802"},{"key":"111_CR28","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1002\/(SICI)1097-0118(200003)33:3<167::AID-JGT7>3.0.CO;2-5","volume":"33","author":"D. Peleg","year":"2000","unstructured":"Peleg, D.: Proximity-preserving labeling schemes. Journal of Graph Theory\u00a033, 167\u2013176 (2000)","journal-title":"Journal of Graph Theory"},{"key":"111_CR29","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/0020-0190(94)90053-1","volume":"49","author":"C.J. Rhee","year":"1994","unstructured":"Rhee, C.J., Liang, Y.D., Dhall, S.K., Lakshmivarahan, S.: Efficient algorithms for finding depth-first and breadth-first search trees in permutation graphs. Information Processing Letters\u00a049, 45\u201350 (1994)","journal-title":"Information Processing Letters"},{"key":"111_CR30","first-page":"281","volume-title":"36 th STOC","author":"K. Talwar","year":"2004","unstructured":"Talwar, K.: Bypassing the embedding: Algorithms for low dimensional metrics. In: 36 th STOC, pp. 281\u2013290. ACM Press, New York (2004)"},{"key":"111_CR31","first-page":"242","volume-title":"42nd FOCS","author":"M. Thorup","year":"2001","unstructured":"Thorup, M.: Compact oracles for reachability and approximate distances in planar digraphs. In: 42nd FOCS, pp. 242\u2013251. IEEE Computer Society Press, Los Alamitos (2001)"},{"key":"111_CR32","first-page":"183","volume-title":"33rd Annual ACM Symp. on Theory of Computing (STOC)","author":"M. Thorup","year":"2001","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. In: 33rd Annual ACM Symp. on Theory of Computing (STOC), pp. 183\u2013192. ACM Press, New York (2001)"},{"key":"111_CR33","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1137\/0603036","volume":"3","author":"M. Yannakakis","year":"1982","unstructured":"Yannakakis, M.: The complexity of the parital order dimension problem. SIAM Journal on Algebraic and Discrete Methods\u00a03, 351\u2013358 (1982)","journal-title":"SIAM Journal on Algebraic and Discrete Methods"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11602613_111.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:02:34Z","timestamp":1619506954000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11602613_111"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540309352","9783540324263"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/11602613_111","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}