{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:47:10Z","timestamp":1725536830203},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642038150"},{"type":"electronic","value":"9783642038167"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-03816-7_25","type":"book-chapter","created":{"date-parts":[[2009,8,19]],"date-time":"2009-08-19T14:43:03Z","timestamp":1250692983000},"page":"282-294","source":"Crossref","is-referenced-by-count":1,"title":["How to Use Spanning Trees to Navigate in Graphs"],"prefix":"10.1007","author":[{"given":"Feodor F.","family":"Dragan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yang","family":"Xiang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"25_CR1","first-page":"48","volume-title":"3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communic.","author":"P. Bose","year":"1999","unstructured":"Bose, P., Morin, P., Stojmenovic, I., Urrutia, J.: Routing with guaranteed delivery in ad hoc wireless networks. In: 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communic., pp. 48\u201355. ACM Press, New York (1999)"},{"key":"25_CR2","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1137\/S0895480193253415","volume":"11","author":"A. Brandst\u00e4dt","year":"1998","unstructured":"Brandst\u00e4dt, A., Dragan, F.F., Chepoi, V.D., Voloshin, V.I.: Dually chordal graphs. SIAM J. Discrete Math.\u00a011, 437\u2013455 (1998)","journal-title":"SIAM J. Discrete Math."},{"key":"25_CR3","doi-asserted-by":"crossref","unstructured":"Brandst\u00e4dt, A., Bang Le, V., Spinrad, J.P.: Graph Classes: A Survey, Philadelphia. SIAM Monographs on Discrete Mathematics and Applications (1999)","DOI":"10.1137\/1.9780898719796"},{"key":"25_CR4","doi-asserted-by":"crossref","unstructured":"Chepoi, V., Dragan, F.F., Estellon, B., Habib, M., Vax\u00e8s, Y.: Diameters, centers, and approximating trees of \u03b4-hyperbolic geodesic spaces and graphs. In: SoCG 2008, pp. 59\u201368 (2008)","DOI":"10.1145\/1377676.1377687"},{"key":"25_CR5","doi-asserted-by":"publisher","first-page":"2008","DOI":"10.1016\/j.disc.2005.12.060","volume":"307","author":"Y. Dourisboure","year":"2007","unstructured":"Dourisboure, Y., Gavoille, C.: Tree-decompositions with bags of small diameter. Discrete Mathematics\u00a0307, 2008\u20132029 (2007)","journal-title":"Discrete Mathematics"},{"key":"25_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"788","DOI":"10.1007\/978-3-540-92182-0_69","volume-title":"Algorithms and Computation","author":"F.F. Dragan","year":"2008","unstructured":"Dragan, F.F., Matamala, M.: Navigating in a graph by aid of its spanning tree. In: Hong, S.-H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC 2008. LNCS, vol.\u00a05369, pp. 788\u2013799. Springer, Heidelberg (2008)"},{"key":"25_CR7","doi-asserted-by":"crossref","unstructured":"Dragan, F.F., Xiang, Y.: How to use spanning trees to navigate in graphs, full version, http:\/\/www.cs.kent.edu\/~dragan\/MFCS2009-journal.pdf","DOI":"10.1007\/978-3-642-03816-7_25"},{"key":"25_CR8","unstructured":"Fonseca, R., Ratnasamy, S., Zhao, J., Ee, C.T., Culler, D., Shenker, S., Stoica, I.: Beacon vector routing: Scalable point-to-point routing in wireless sensornets. In: 2nd USENIX\/ACM Symp. on Networked Systems Design and Implementation (2005)"},{"key":"25_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/978-3-540-75520-3_2","volume-title":"Algorithms \u2013 ESA 2007","author":"P. Fraigniaud","year":"2007","unstructured":"Fraigniaud, P.: Small Worlds as Navigable Augmented Networks: Model, Analysis, and Validation. In: Arge, L., Hoffmann, M., Welzl, E. (eds.) ESA 2007. LNCS, vol.\u00a04698, pp. 2\u201311. Springer, Heidelberg (2007)"},{"key":"25_CR10","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Korman, A., Lebhar, E.: Local MST computation with short advice. In: SPAA 2007, 154\u2013160 (2007)","DOI":"10.1145\/1248377.1248402"},{"key":"25_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"606","DOI":"10.1007\/11549468_68","volume-title":"Euro-Par 2005 Parallel Processing","author":"V.K. Garg","year":"2005","unstructured":"Garg, V.K., Agarwal, A.: Distributed maintenance of a spanning tree using labeled tree encoding. In: Cunha, J.C., Medeiros, P.D. (eds.) Euro-Par 2005. LNCS, vol.\u00a03648, pp. 606\u2013616. Springer, Heidelberg (2005)"},{"key":"25_CR12","unstructured":"Gartner, F.C.: A Survey of Self-Stabilizing Spanning-Tree Construction Algorithms, Technical Report IC\/2003\/38, Swiss Federal Institute of Technology (EPFL) (2003)"},{"key":"25_CR13","doi-asserted-by":"crossref","unstructured":"Gavoille, C.: Routing in distributed networks: Overview and open problems. ACM SIGACT News - Distributed Computing Column\u00a032 (2001)","DOI":"10.1145\/568438.568451"},{"key":"25_CR14","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. J. Algorithms\u00a053, 85\u2013112 (2004)","journal-title":"J. Algorithms"},{"key":"25_CR15","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/978-1-4613-0223-0_4","volume-title":"Ad Hoc Wireless Networking","author":"S. Giordano","year":"2004","unstructured":"Giordano, S., Stojmenovic, I.: Position based routing algorithms for ad hoc networks: A taxonomy. In: Ad Hoc Wireless Networking, pp. 103\u2013136. Kluwer, Dordrecht (2004)"},{"key":"25_CR16","doi-asserted-by":"crossref","unstructured":"Gromov, M.: Hyperbolic Groups. In: Gersten, S.M. (ed.) Essays in group theory. MSRI Series, vol.\u00a08, pp. 75\u2013263 (1987)","DOI":"10.1007\/978-1-4613-9586-7_3"},{"issue":"4","key":"25_CR17","doi-asserted-by":"publisher","first-page":"723","DOI":"10.1145\/502090.502095","volume":"48","author":"J. Holm","year":"2001","unstructured":"Holm, J., de Lichtenberg, K., Thorup, M.: Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM\u00a048(4), 723\u2013760 (2001)","journal-title":"J. ACM"},{"key":"25_CR18","doi-asserted-by":"crossref","unstructured":"Jacquet, P., Viennot, L.: Remote spanners: what to know beyond neighbors. In: IPDPS 2009, pp. 1\u201315 (2009)","DOI":"10.1109\/IPDPS.2009.5161041"},{"key":"25_CR19","first-page":"243","volume-title":"6th ACM\/IEEE MobiCom.","author":"B. Karp","year":"2000","unstructured":"Karp, B., Kung, H.T.: GPSR: greedy perimeter stateless routing for wireless networks. In: 6th ACM\/IEEE MobiCom., pp. 243\u2013254. ACM Press, New York (2000)"},{"key":"25_CR20","first-page":"163","volume-title":"STOC 2000","author":"J.M. Kleinberg","year":"2000","unstructured":"Kleinberg, J.M.: The small-world phenomenon: an algorithm perspective. In: STOC 2000, pp. 163\u2013170. ACM, New York (2000)"},{"key":"25_CR21","doi-asserted-by":"crossref","unstructured":"Kleinberg, R.: Geographic routing using hyperbolic space. In: INFOCOM 2007, pp. 1902\u20131909 (2007)","DOI":"10.1109\/INFCOM.2007.221"},{"key":"25_CR22","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1145\/872035.872044","volume-title":"PODC","author":"F. Kuhn","year":"2003","unstructured":"Kuhn, F., Wattenhofer, R., Zhang, Y., Zollinger, A.: Geometric ad-hoc routing: of theory and practice. In: PODC, pp. 63\u201372. ACM, New York (2003)"},{"key":"25_CR23","doi-asserted-by":"publisher","first-page":"11623","DOI":"10.1073\/pnas.0503018102","volume":"102","author":"D. Liben-Nowell","year":"2005","unstructured":"Liben-Nowell, D., Novak, J., Kumar, R., Raghavan, P., Tomkins, A.: Geographic routing in social networks. PNAS\u00a0102, 11623\u201311628 (2005)","journal-title":"PNAS"},{"key":"25_CR24","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/BF01200757","volume":"15","author":"N. Linial","year":"1995","unstructured":"Linial, N., London, E., Rabinovich, Y.: The Geometry of Graphs and Some of its Algorithmic Applications. Combinatorica\u00a015, 215\u2013245 (1995)","journal-title":"Combinatorica"},{"key":"25_CR25","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 and Their Applications. J. of Graph Theory\u00a033, 167\u2013176 (2000)","journal-title":"J. of Graph Theory"},{"key":"25_CR26","series-title":"SIAM Monographs on Discrete Math. Appl.","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-Sensitive Approach","author":"D. Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM Monographs on Discrete Math. Appl. SIAM, Philadelphia (2000)"},{"key":"25_CR27","doi-asserted-by":"crossref","unstructured":"Rao, A., Papadimitriou, C., Shenker, S., Stoica, I.: Geographical routing without location information. In: Proceedings of MobiCom 2003, pp. 96\u2013108 (2003)","DOI":"10.1145\/938994.938996"},{"key":"25_CR28","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. Journal of Algorithms\u00a07, 309\u2013322 (1986)","journal-title":"Journal of Algorithms"},{"issue":"1","key":"25_CR29","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1093\/comjnl\/28.1.5","volume":"28","author":"N. Santoro","year":"1985","unstructured":"Santoro, N., Khatib, R.: Labelling and Implicit Routing in Networks. The Computer Journal\u00a028(1), 5\u20138 (1985)","journal-title":"The Computer Journal"},{"key":"25_CR30","unstructured":"Shavitt, Y., Tankel, T.: On internet embedding in hyperbolic spaces for overlay construction and distance estimation. In: INFOCOM 2004 (2004)"},{"key":"25_CR31","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: 13th Ann. ACM Symp. on Par. Alg. and Arch., July 2001, pp. 1\u201310 (2001)","DOI":"10.1145\/378580.378581"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03816-7_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T11:23:28Z","timestamp":1685100208000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03816-7_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642038150","9783642038167"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03816-7_25","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}