{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T08:25:35Z","timestamp":1648542335324},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2012,4,18]],"date-time":"2012-04-18T00:00:00Z","timestamp":1334707200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2013,7]]},"DOI":"10.1007\/s00453-012-9647-1","type":"journal-article","created":{"date-parts":[[2012,4,17]],"date-time":"2012-04-17T14:57:35Z","timestamp":1334674655000},"page":"479-511","source":"Crossref","is-referenced-by-count":0,"title":["How to Use Spanning Trees to Navigate in Graphs"],"prefix":"10.1007","volume":"66","author":[{"given":"Feodor F.","family":"Dragan","sequence":"first","affiliation":[]},{"given":"Yang","family":"Xiang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,4,18]]},"reference":[{"key":"9647_CR1","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1145\/1281100.1281110","volume-title":"Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing (PODC 2007)","author":"I. Abraham","year":"2007","unstructured":"Abraham, I., Balakrishnan, M., Kuhn, F., Malkhi, D., Ramasubramanian, V., Talwar, K.: Reconstructing approximate tree metrics. In: Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing (PODC 2007), Portland, Oregon, USA August 12\u201315, 2007 pp. 43\u201352. ACM, New York (2007)"},{"key":"9647_CR2","volume-title":"Local Search in Unstructured Networks","author":"L.A. Adamic","year":"2002","unstructured":"Adamic, L.A., Lukose, R.M., Huberman, B.A.: Local Search in Unstructured Networks. Willey, New York (2002)"},{"issue":"046135","key":"9647_CR3","first-page":"1","volume":"64","author":"L.A. Adamic","year":"2001","unstructured":"Adamic, L.A., Lucose, R.M., Puniyani, A.R., Huberman, B.A.: Search in power-law networks. Phys. Rev. E 64(046135), 1\u20138 (2001)","journal-title":"Phys. Rev. E"},{"key":"9647_CR4","first-page":"3","volume-title":"Group Theory from a Geometrical Viewpoint","author":"J.M. Alonso","year":"1991","unstructured":"Alonso, J.M., Brady, T., Cooper, D., Ferlini, V., Lustig, M., Mihalik, M., Shapiro, M., Short, H.: Notes on word hyperbolic groups. In: Ghys, E., Haefliger, A., Verjovsky, A. (eds.) Group Theory from a Geometrical Viewpoint, ICTP, Trieste 1990, pp. 3\u201363. World Scientific, Singapore (1991)"},{"key":"9647_CR5","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1145\/313239.313282","volume-title":"Proceedings of the 3rd International Workshop on Discrete algorithms and Methods for Mobile Computing and Communications","author":"P. Bose","year":"1999","unstructured":"Bose, P., Morin, P., Stojmenovic, I., Urrutia, J.: Routing with guaranteed delivery in ad hoc wireless networks. In: Proceedings of the 3rd International Workshop on Discrete algorithms and Methods for Mobile Computing and Communications, pp. 48\u201355. ACM Press, New York (1999)"},{"key":"9647_CR6","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/S0166-218X(97)00125-X","volume":"82","author":"A. Brandst\u00e4dt","year":"1998","unstructured":"Brandst\u00e4dt, A., Chepoi, V.D., Dragan, F.F.: The algorithmic use of hypertree structure and maximum neighbourhood orderings. Discrete Appl. Math. 82, 43\u201377 (1998)","journal-title":"Discrete Appl. Math."},{"key":"9647_CR7","doi-asserted-by":"crossref","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. 11, 437\u2013455 (1998)","journal-title":"SIAM J. Discrete Math."},{"key":"9647_CR8","series-title":"SIAM Monographs on Discrete Mathematics and Applications","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A. Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le Bang, V., Spinrad, J.P.: In: Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia (1999)"},{"key":"9647_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-12494-9","volume-title":"Metric Spaces of Non-Positive Curvature","author":"M. Bridson","year":"1999","unstructured":"Bridson, M., Haefliger, A.: Metric Spaces of Non-Positive Curvature. Springer, Berlin (1999)"},{"key":"9647_CR10","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: Proceedings of the 24th Annual ACM Symposium on Computational Geometry, June 9\u201311 (2008)","DOI":"10.1016\/j.endm.2008.06.046"},{"key":"9647_CR11","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1007\/s00453-010-9478-x","volume":"62","author":"V. Chepoi","year":"2012","unstructured":"Chepoi, V., Dragan, F.F., Estellon, B., Habib, M., Vax\u00e8s, Y., Xiang, Y.: Additive spanners and distance and routing labeling schemes for \u03b4-Hyperbolic graphs. Algorithmica 62, 713\u2013732 (2012)","journal-title":"Algorithmica"},{"key":"9647_CR12","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1002\/net.10098","volume":"42","author":"D.G. Corneil","year":"2003","unstructured":"Corneil, D.G., Dragan, F.F., K\u00f6hler, E.: On the power of BFS to determine a graph\u2019s diameter. Networks 42, 209\u2013222 (2003)","journal-title":"Networks"},{"key":"9647_CR13","unstructured":"Corneil, D.G., Dragan, F.F., K\u00f6hler, E., Xiang, Y.: Lower bounds for collective additive tree spanners. In preparation"},{"key":"9647_CR14","series-title":"Graduate Texts in Mathematics","volume-title":"Graph Theory","author":"R. Diestel","year":"2000","unstructured":"Diestel, R.: Graph Theory, 2nd edn. Graduate Texts in Mathematics, vol. 173. Springer, Berlin (2000)","edition":"2"},{"key":"9647_CR15","doi-asserted-by":"crossref","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 Math. 307, 2008\u20132029 (2007)","journal-title":"Discrete Math."},{"key":"9647_CR16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.jalgor.2004.09.002","volume":"57","author":"F.F. Dragan","year":"2005","unstructured":"Dragan, F.F.: Estimating all pairs shortest paths in restricted graph families: A unified approach. J. Algorithms 57, 1\u201321 (2005)","journal-title":"J. Algorithms"},{"key":"9647_CR17","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1137\/090761549","volume":"25","author":"F.F. Dragan","year":"2011","unstructured":"Dragan, F.F., Matamala, M.: Navigating in a graph by aid of its spanning tree metric. SIAM J. Discrete Math. 25, 306\u2013332 (2011)","journal-title":"SIAM J. Discrete Math."},{"key":"9647_CR18","doi-asserted-by":"crossref","first-page":"1282","DOI":"10.1016\/j.jcss.2006.07.002","volume":"72","author":"M. Elkin","year":"2006","unstructured":"Elkin, M.: A faster distributed protocol for constructing a minimum spanning tree. J. Comput. Syst. Sci. 72, 1282\u20131308 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"9647_CR19","volume-title":"Proceedings of the Second USENIX\/ACM Symposium on Networked Systems Design and Implementation (NSDI 2005)","author":"R. Fonseca","year":"2005","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: Proceedings of the Second USENIX\/ACM Symposium on Networked Systems Design and Implementation (NSDI 2005) (2005)"},{"key":"9647_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1007\/978-3-540-75520-3_2","volume-title":"Proceedings of the 15th Annual European Symposium","author":"P. Fraigniaud","year":"2007","unstructured":"Fraigniaud, P.: Small worlds as navigable augmented networks: model, analysis, and validation. In: Proceedings of the 15th Annual European Symposium, ESA 2007, Eilat, Israel, October 8\u201310, 2007. Lecture Notes in Computer Science, vol. 4698, pp. 2\u201311. Springer, Berlin (2007). 2007"},{"key":"9647_CR21","doi-asserted-by":"crossref","first-page":"920","DOI":"10.1007\/s00224-010-9280-9","volume":"47","author":"P. Fraigniaud","year":"2010","unstructured":"Fraigniaud, P., Korman, A., Lebhar, E.: Local MST computation with short advice. Theory Comput. Syst. 47, 920\u2013933 (2010)","journal-title":"Theory Comput. Syst."},{"key":"9647_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1007\/11549468_68","volume-title":"Processing of Euro-Par 2005","author":"V.K. Garg","year":"2005","unstructured":"Garg, V.K., Agarwal, A.: Distributed maintenance of a spanning tree using labeled tree encoding. In: Processing of Euro-Par 2005. Lecture Notes in Computer Science, vol. 3648, pp. 606\u2013616 (2005)"},{"key":"9647_CR23","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":"9647_CR24","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1016\/S0304-3975(99)00283-2","volume":"245","author":"C. Gavoille","year":"1999","unstructured":"Gavoille, C.: A survey on interval routing schemes. Theor. Comput. Sci. 245, 217\u2013253 (1999)","journal-title":"Theor. Comput. Sci."},{"key":"9647_CR25","doi-asserted-by":"crossref","unstructured":"Gavoille, C.: Routing in distributed networks: overview and open problems. ACM SIGACT News-Distribute Comput. Column 32 (2001)","DOI":"10.1145\/568438.568451"},{"key":"9647_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"476","DOI":"10.1007\/3-540-44676-1_40","volume-title":"Approximate distance labeling schemes","author":"C. Gavoille","year":"2001","unstructured":"Gavoille, C., Katz, M., Katz, N.A., Paul, C., Peleg, D.: In: Approximate distance labeling schemes, 9th Annual European Symposium on Algorithms, ESA. Lecture Notes in Computer Science, vol. 2161, pp. 476\u2013488. Springer, Berlin (2001)"},{"key":"9647_CR27","doi-asserted-by":"crossref","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 53, 85\u2013112 (2004)","journal-title":"J. Algorithms"},{"key":"9647_CR28","series-title":"Progress in Mathematics","volume-title":"Les Groupes Hyperboliques d\u2019apr\u00e8s M. Gromov","year":"1990","unstructured":"Ghys, E., de la Harpe, P. (eds.): Les Groupes Hyperboliques d\u2019apr\u00e8s M. Gromov. Progress in Mathematics, vol. 83. Birkh\u00e4user, Basel (1990)"},{"key":"9647_CR29","doi-asserted-by":"crossref","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: Cheng, X., Huang, X., Du, D. (eds.) Ad Hoc Wireless Networking, pp. 103\u2013136. Kluwer, Amsterdam (2004)"},{"key":"9647_CR30","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M.C. Golumbic","year":"1980","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980)"},{"key":"9647_CR31","series-title":"MSRI Series","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/978-1-4613-9586-7_3","volume-title":"Essays in group theory","author":"M. Gromov","year":"1987","unstructured":"Gromov, M.: Hyperbolic groups. In: Gersten, S.M. (ed.) Essays in group theory. MSRI Series, vol. 8, pp. 75\u2013263 (1987)"},{"key":"9647_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"594","DOI":"10.1007\/3-540-63165-8_214","volume-title":"Proceedings of 24th International Colloquium on Automata, Languages and Programming (ICALP\u201997)","author":"M.R. Henzinger","year":"1997","unstructured":"Henzinger, M.R., King, V.: Maintaining minimum spanning trees in dynamic graphs. In: Proceedings of 24th International Colloquium on Automata, Languages and Programming (ICALP\u201997), Bologna, Italy, 7\u201311, July 1997. Lecture Notes in Computer Science, vol. 1256, pp. 594\u2013604. Springer, Berlin (1997)"},{"key":"9647_CR33","doi-asserted-by":"crossref","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 48, 723\u2013760 (2001)","journal-title":"J. ACM"},{"key":"9647_CR34","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/IPDPS.2009.5161041","volume-title":"23rd IEEE International Parallel and Distributed Processing Symposium (IPDPS 2009)","author":"P. Jacquet","year":"2009","unstructured":"Jacquet, P., Viennot, L.: Remote spanners: what to know beyond neighbors. In: 23rd IEEE International Parallel and Distributed Processing Symposium (IPDPS 2009), pp. 1\u201315 (2009)"},{"key":"9647_CR35","first-page":"243","volume-title":"Proceedings of the 6th ACM\/IEEE MobiCom","author":"B. Karp","year":"2000","unstructured":"Karp, B., Kung, H.T.: GPSR: greedy perimeter stateless routing for wireless networks. In: Proceedings of the 6th ACM\/IEEE MobiCom, pp. 243\u2013254. ACM, New York (2000)"},{"key":"9647_CR36","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.M.: The small-world phenomenon: an algorithm perspective. In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC 2000), May 21\u201323 (2000)","DOI":"10.1145\/335305.335325"},{"key":"9647_CR37","doi-asserted-by":"crossref","first-page":"1902","DOI":"10.1109\/INFCOM.2007.221","volume-title":"Proceedings of the 26th IEEE International Conference on Computer Communications (INFOCOM 2007)","author":"R. Kleinberg","year":"2007","unstructured":"Kleinberg, R.: Geographic routing using hyperbolic space. In: Proceedings of the 26th IEEE International Conference on Computer Communications (INFOCOM 2007), Anchorage, AK pp. 1902\u20131909. IEEE, New York (2007)"},{"key":"9647_CR38","first-page":"63","volume-title":"Proceedings of the 22nd Annual Symposium on Principles of Distributed Computing","author":"F. Kuhn","year":"2003","unstructured":"Kuhn, F., Wattenhofer, R., Zhang, Y., Zollinger, A.: Geometric ad-hoc routing: of theory and practice. In: Proceedings of the 22nd Annual Symposium on Principles of Distributed Computing, pp. 63\u201372. ACM, New York (2003)"},{"key":"9647_CR39","doi-asserted-by":"crossref","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. Proc. Natl. Acad. Sci. USA 102, 11623\u201311628 (2005)","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"9647_CR40","doi-asserted-by":"crossref","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 15, 215\u2013245 (1995)","journal-title":"Combinatorica"},{"key":"9647_CR41","doi-asserted-by":"crossref","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. Graph Theory 33, 167\u2013176 (2000)","journal-title":"J. Graph Theory"},{"key":"9647_CR42","series-title":"SIAM Monographs on Discrete Math. Appl.","doi-asserted-by":"crossref","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":"9647_CR43","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1145\/938985.938996","volume-title":"Proceedings of the 9th Annual International Conference on Mobile Computing and Networking (MobiCom 2003)","author":"A. Rao","year":"2003","unstructured":"Rao, A., Papadimitriou, C., Shenker, S., Stoica, I.: Geographical routing without location information. In: Proceedings of the 9th Annual International Conference on Mobile Computing and Networking (MobiCom 2003), pp. 96\u2013108 (2003)"},{"key":"9647_CR44","doi-asserted-by":"crossref","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. J. Algorithms 7, 309\u2013322 (1986)","journal-title":"J. Algorithms"},{"key":"9647_CR45","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"D. Rose","year":"1976","unstructured":"Rose, D., Tarjan, R.E., Lueker, G.: Algorithmic aspects on vertex elimination on graphs. SIAM J. Comput. 5, 266\u2013283 (1976)","journal-title":"SIAM J. Comput."},{"key":"9647_CR46","doi-asserted-by":"crossref","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. Comput. J. 28, 5\u20138 (1985)","journal-title":"Comput. J."},{"key":"9647_CR47","first-page":"7","volume-title":"Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2004)","author":"Y. Shavitt","year":"2004","unstructured":"Shavitt, Y., Tankel, T.: On internet embedding in hyperbolic spaces for overlay construction and distance estimation. In: Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2004), Hong Kong, China, March 7\u201311, 2004, pp. 7\u201311. IEEE, New York (2004)"},{"key":"9647_CR48","first-page":"1","volume-title":"Proceedings of the 13th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA 2001)","author":"M. Thorup","year":"2001","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: Proceedings of the 13th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA 2001), Heraklion, Crete Island, Greece, July 4\u20136, 2001, pp. 1\u201310. ACM, New York (2001)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9647-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-012-9647-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-012-9647-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,13]],"date-time":"2022-01-13T02:37:50Z","timestamp":1642041470000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-012-9647-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,4,18]]},"references-count":48,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,7]]}},"alternative-id":["9647"],"URL":"https:\/\/doi.org\/10.1007\/s00453-012-9647-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,4,18]]}}}