{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T20:53:06Z","timestamp":1725483186187},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540000730"},{"type":"electronic","value":"9783540361084"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-36108-1_17","type":"book-chapter","created":{"date-parts":[[2007,5,3]],"date-time":"2007-05-03T20:38:36Z","timestamp":1178224716000},"page":"252-264","source":"Crossref","is-referenced-by-count":9,"title":["Improved Compact Routing Scheme for Chordal Graphs"],"prefix":"10.1007","author":[{"given":"Yon","family":"Dourisboure","sequence":"first","affiliation":[]},{"given":"Cyril","family":"Gavoille","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,10,24]]},"reference":[{"key":"17_CR1","doi-asserted-by":"crossref","unstructured":"Baruch Awerbuch, Amotz Bar-Noy, Nathan Linial, and David Peleg. Compact distributed data structures for adaptive routing. In 21st Symposium on Theory of Computing (STOC), volume 2, pages 230\u2013240, May 1989.","DOI":"10.1145\/73007.73053"},{"key":"17_CR2","doi-asserted-by":"crossref","unstructured":"Baruch Awerbuch, Amotz Bar-Noy, Nathan Linial, and David Peleg. Improved routing strategies with succinct tables. Journal of Algorithms, 11(3):307\u2013341, September 1990.","DOI":"10.1016\/0196-6774(90)90017-9"},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"Baruch Awerbuch and David Peleg. Sparse partitions. In 31th Symposium on Foundations of Computer Science (FOCS), pages 503\u2013513. IEEE Computer Society Press, 1990.","DOI":"10.1109\/FSCS.1990.89571"},{"issue":"2","key":"17_CR4","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1137\/0405013","volume":"5","author":"Baruch Awerbuch","year":"1992","unstructured":"Baruch Awerbuch and David Peleg. Routing with polynomial communication-space trade-off. SIAM Journal on Discrete Mathematics, 5(2):151\u2013162, May 1992.","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"17_CR5","unstructured":"Stephen Alstrup and Theis Rauhe. Improved labeling scheme for ancestor queries. In 13th Symposium on Discrete Algorithms (SODA). ACM-SIAM, January 2001. To appear."},{"key":"17_CR6","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1006\/jagm.1998.0962","volume":"30","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"Andreas Brandst\u00e4dt, Victor Chepoi, and Feodor Dragan. Distance approximating trees for chordal and dually chordal graphs. Journal of Algorithms, 30:166\u2013184, 1999.","journal-title":"Journal of Algorithms"},{"key":"17_CR7","doi-asserted-by":"crossref","unstructured":"Reinhard Diestel. Graph Theory (second edition), volume 173 of Graduate Texts in Mathematics. Springer, February 2000.","DOI":"10.1007\/978-3-662-53622-3_7"},{"key":"17_CR8","doi-asserted-by":"crossref","unstructured":"Yon Dourisboure. An additive stretched routing scheme for chordal graphs. In 28-th International Workshop on Graph-Theoretic Concepts in Computer Science (WG\u2019 02), June 2002. To appear.","DOI":"10.1007\/3-540-36379-3_14"},{"key":"17_CR9","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/s004460050025","volume":"10","author":"P. Fraigniaud","year":"1997","unstructured":"Pierre Fraigniaud and Cyril Gavoille. Universal routing schemes. Journal of Distributed Computing, 10:65\u201378, 1997.","journal-title":"Journal of Distributed Computing"},{"key":"17_CR10","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"757","DOI":"10.1007\/3-540-48224-5_62","volume-title":"28th International Colloquium on Automata, Languages and Programming (ICALP)","author":"P. Fraigniaud","year":"2001","unstructured":"Pierre Fraigniaud and Cyril Gavoille. Routing in trees. In Fernando Orejas, Paul G. Spirakis, and Jan van Leeuwen, editors, 28th International Colloquium on Automata, Languages and Programming (ICALP), volume 2076 of Lecture Notes in Computer Science, pages 757\u2013772. Springer, July 2001."},{"key":"17_CR11","doi-asserted-by":"crossref","unstructured":"Greg N. Frederickson and Ravi Janardan. Efficient message routing in planar networks. SIAM Journal on Computing, 18(4):843\u2013857, August 1989.","DOI":"10.1137\/0218058"},{"key":"17_CR12","doi-asserted-by":"crossref","unstructured":"Greg N. Frederickson and Ravi Janardan. Space-efficient message routing in c-decomposable networks. SIAM Journal on Computing, 19(1):164\u2013181, February 1990.","DOI":"10.1137\/0219011"},{"key":"17_CR13","doi-asserted-by":"crossref","unstructured":"Cyril Gavoille. Routing in distributed networks: Overview and open problems. ACM SIGACT News-Distributed Computing Column, 32(1), March 2001. To appear.","DOI":"10.1145\/568438.568451"},{"key":"17_CR14","doi-asserted-by":"publisher","first-page":"679","DOI":"10.1006\/jpdc.2000.1705","volume":"61","author":"C. Gavoille","year":"2001","unstructured":"Cyril Gavoille and Marc Gengler. Space-efficiency of routing schemes of stretch factor three. Journal of Parallel and Distributed Computing, 61:679\u2013687, 2001.","journal-title":"Journal of Parallel and Distributed Computing"},{"key":"17_CR15","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/3-540-48523-6_32","volume-title":"26th International Colloquium on Automata, Languages and Programming (ICALP)","author":"C. Gavoille","year":"1999","unstructured":"Cyril Gavoille and Nicolas Hanusse. Compact routing tables for graphs of bounded genus. In Ji\u0159\u00ed Wiedermann, Peter van Emde Boas, and Mogens Nielsen, editors, 26 th International Colloquium on Automata, Languages and Programming (ICALP), volume 1644 of Lecture Notes in Computer Science, pages 351\u2013360. Springer, July 1999."},{"key":"17_CR16","volume-title":"Research Report RR-1250-00","author":"C. Gavoille","year":"2000","unstructured":"Cyril Gavoille, Michal Katz, Nir A. Katz, Christophe Paul, and David Peleg. Approximate distance labeling schemes. Research Report RR-1250-00, LaBRI, University of Bordeaux, 351, cours de la Lib\u00e9ration, 33405 Talence Cedex, France, December 2000."},{"key":"17_CR17","doi-asserted-by":"crossref","unstructured":"Cyril Gavoille and St\u00e9phane P\u00e9renn\u00e8s. Memory requirement for routing in distributed networks. In 15 th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 125\u2013133. ACM PRESS, May 1996.","DOI":"10.1145\/248052.248075"},{"key":"17_CR18","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/3-540-44634-6_23","volume-title":"7th International Workshop on Algorithms and Data Structures (WADS)","author":"H. Kaplan","year":"2001","unstructured":"Haim Kaplan and Tova Milo. Short and simple labels for small distances and other functions. In 7 th International Workshop on Algorithms and Data Structures (WADS), volume 2125 of Lecture Notes in Computer Science, pages 32\u201340. Springer, August 2001."},{"key":"17_CR19","unstructured":"Haim Kaplan, Tova Milo, and Ronen Shabo. A comparison of labeling schemes for ancestor queries. In 14th Symposium on Discrete Algorithms (SODA). ACM-SIAM, January 2002."},{"key":"17_CR20","unstructured":"Frank Thomson Leighton. Introduction to Parallel Algorithms and Architectures: Arrays-Trees-Hypercubes. Morgan Kaufmann, 1992."},{"key":"17_CR21","unstructured":"Hsueh-I Lu. Improved comact routing tabels for planar networks via orderly spanning trees. In 8 th Annual International Computing & Combinatorics Conference (COCOON), volume Lectures Notes in Computer Science. Springer, August 2002."},{"issue":"2","key":"17_CR22","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1006\/jagm.1997.0880","volume":"26","author":"Lata Narayanan and Naomi Nishimura","year":"1998","unstructured":"Lata Narayanan and Naomi Nishimura. Interval routing on k-trees. Journalf Algorithms, 26(2):325\u2013369, February 1998.","journal-title":"Journalf Algorithms"},{"key":"17_CR23","doi-asserted-by":"crossref","unstructured":"David Peleg. Distributed Computing: A Locality-S ensitive Approach. SIAM Monographs on Discrete Mathematics and Applications, 2000.","DOI":"10.1137\/1.9780898719772"},{"key":"17_CR24","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1007\/3-540-44612-5_53","volume-title":"25th International Symposium on Mathematical Foundations of Computer Science (MFCS)","author":"D. Peleg","year":"2000","unstructured":"David Peleg. Informative labeling schemes for graphs. In 25th International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 1893 of Lecture Notes in Computer Science, pages 579\u2013588. Springer, August 2000."},{"key":"17_CR25","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1007\/BFb0023484","volume-title":"14th Annual Symposium on Theoretical Aspects of Computer Science (STACS)","author":"E. Prisner","year":"1997","unstructured":"Erich Prisner. Distance approximating spanning trees. In 14 th Annual Symposium on Theoretical Aspects of Computer Science (STACS), volume 1200 of Lecture Notes in Computer Science, pages 499\u2013510. Springer, 1997."},{"issue":"1","key":"17_CR26","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"13","author":"D. Peleg","year":"1989","unstructured":"David Peleg and Alejandro A. Sch\u00e4ffer. Graph spanners. Journal of Graph Theory, 13(1):99\u2013116, 1989.","journal-title":"Journal of Graph Theory"},{"issue":"3","key":"17_CR27","doi-asserted-by":"crossref","first-page":"510","DOI":"10.1145\/65950.65953","volume":"36","author":"David Peleg","year":"1989","unstructured":"David Peleg and Eli Upfal. A trade-off between space and efficiency for routing tables. Journal of the ACM, 36(3):510\u2013530, July 1989.","journal-title":"Journal of the ACM"},{"key":"17_CR28","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Neil Robertson and Paul D. Seymour. Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms, 7:309\u2013322, 1986.","journal-title":"Journal of Algorithms"},{"key":"17_CR29","doi-asserted-by":"crossref","unstructured":"Mikkel Thorup. Compact oracles for reachability and approximate distances in planar digraphs. In 42 th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society Press, October 2001.","DOI":"10.1109\/SFCS.2001.959898"},{"key":"17_CR30","doi-asserted-by":"crossref","unstructured":"Mikkel Thorup and Uri Zwick. Approximate distance oracles. In 33rd Annual ACM Symposium on Theory of Computing (STOC), pages 183\u2013192, Hersonissos, Crete, Greece, July 2001.","DOI":"10.1145\/380752.380798"},{"key":"17_CR31","doi-asserted-by":"crossref","unstructured":"Mikkel Thorup and Uri Zwick. Compact routing schemes. In 13 th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pages 1\u201310, Hersonissos, Crete, Greece, July 2001. ACM PRESS.","DOI":"10.1145\/378580.378581"}],"container-title":["Lecture Notes in Computer Science","Distributed Computing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-36108-1_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T14:17:45Z","timestamp":1556374665000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-36108-1_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540000730","9783540361084"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/3-540-36108-1_17","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}