{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:25:07Z","timestamp":1725549907445},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540291183"},{"type":"electronic","value":"9783540319511"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11561071_70","type":"book-chapter","created":{"date-parts":[[2005,10,6]],"date-time":"2005-10-06T12:46:24Z","timestamp":1128602784000},"page":"791-802","source":"Crossref","is-referenced-by-count":33,"title":["Greedy Routing in Tree-Decomposed Graphs"],"prefix":"10.1007","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"70_CR1","doi-asserted-by":"crossref","unstructured":"Adamic, L., Adar, E.: How To Search a Social Network. Social Networks. Preprint submitted to Social Networks (2004)","DOI":"10.1016\/j.socnet.2005.01.007"},{"key":"70_CR2","volume-title":"Quantitative Applications in the Social Sciences","author":"M. Aldenderfer","year":"1984","unstructured":"Aldenderfer, M., Blashfield, R.: Cluster Analysis. In: Quantitative Applications in the Social Sciences, vol.\u00a044. SAGE Publications, London (1984)"},{"issue":"5","key":"70_CR3","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/174147.169807","volume":"40","author":"S. Arnborg","year":"1993","unstructured":"Arnborg, S., Courcelle, B., Proskurowski, A., Seese, D.: An algebraic theory of graph reduction. Journal of the ACM\u00a040(5), 1134\u20131164 (1993)","journal-title":"Journal of the ACM"},{"key":"70_CR4","doi-asserted-by":"crossref","unstructured":"Aspnes, J., Diamadi, Z., Shah, G.: Fault-Tolerant Routing in Peer-to-Peer Systems. In: 21st ACM Symp. on Principles of Distributed Computing (PODC), pp. 223\u2013232 (2002)","DOI":"10.1145\/571825.571862"},{"key":"70_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1007\/3-540-45414-4_19","volume-title":"Distributed Computing","author":"L. Barri\u00e8re","year":"2001","unstructured":"Barri\u00e8re, L., Fraigniaud, P., Kranakis, E., Krizanc, D.: Efficient Routing in Networks with Long Range Contacts. In: Welch, J.L. (ed.) DISC 2001. LNCS, vol.\u00a02180, pp. 270\u2013284. Springer, Heidelberg (2001)"},{"key":"70_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/BFb0029946","volume-title":"Mathematical Foundations of Computer Science 1997","author":"H. Bodlaender","year":"1997","unstructured":"Bodlaender, H.: Treewidth: algorithmic techniques and results. In: Privara, I., Ru\u017ei\u010dka, P. (eds.) MFCS 1997. LNCS, vol.\u00a01295, pp. 19\u201336. Springer, Heidelberg (1997)"},{"key":"70_CR7","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1006\/jagm.1995.1009","volume":"18","author":"H. Bodlaender","year":"1995","unstructured":"Bodlaender, H., Gilbert, J., Hafsteinsson, H., Kloks, T.: Approximating Treewidth, Pathwidth, Frontsize and Shortest Elimination Trees. Journal of Algorithms\u00a018, 238\u2013255 (1995)","journal-title":"Journal of Algorithms"},{"issue":"1-3","key":"70_CR8","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/S0166-218X(97)00031-0","volume":"79","author":"H. Bodlaender","year":"1997","unstructured":"Bodlaender, H., Thilikos, D.: Treewidth for Graphs with Small Chordality. Discrete Applied Mathematics\u00a079(1-3), 45\u201361 (1997)","journal-title":"Discrete Applied Mathematics"},{"key":"70_CR9","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/S0166-218X(03)00440-2","volume":"136","author":"V. Bouchitt\u00e9","year":"2004","unstructured":"Bouchitt\u00e9, V., Kratsch, D., M\u00fcller, H., Todinca, I.: On treewidth approximations. Discrete Applied Mathematics\u00a0136, 183\u2013196 (2004)","journal-title":"Discrete Applied Mathematics"},{"key":"70_CR10","doi-asserted-by":"crossref","first-page":"066111","DOI":"10.1103\/PhysRevE.70.066111","volume":"70","author":"A. Clauset","year":"2004","unstructured":"Clauset, A., Newman, M., Moore, C.: Finding community structure in very large networks. Phys. Rev. E 70, 066111 (2004)","journal-title":"Phys. Rev. E"},{"issue":"1","key":"70_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/rsa.10042","volume":"21","author":"D. Coppersmith","year":"2002","unstructured":"Coppersmith, D., Gamarnik, D., Sviridenko, M.: The Diameter of a Long-Range Percolation Graph. Random Structures and Algorithms\u00a021(1), 1\u201313 (2002)","journal-title":"Random Structures and Algorithms"},{"key":"70_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/10692760_1","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"B. Courcelle","year":"1998","unstructured":"Courcelle, B., Makowsky, J., Rotics, U.: Linear-time solvable optimization problems on graphs of bounded cliquewidth. In: Hromkovi\u010d, J., S\u00fdkora, O. (eds.) WG 1998. LNCS, vol.\u00a01517, pp. 1\u201316. Springer, Heidelberg (1998)"},{"key":"70_CR13","doi-asserted-by":"publisher","first-page":"827","DOI":"10.1126\/science.1081058","volume":"301","author":"P. Dodds","year":"2003","unstructured":"Dodds, P., Muhamad, R., Watts, D.: An Experimental Study of Search in Global Social Networks. Science\u00a0301, 827\u2013829 (2003)","journal-title":"Science"},{"key":"70_CR14","doi-asserted-by":"crossref","unstructured":"Donetti, L., Mu\u00f1oz, M.: Detecting Network Communities: A New Systematic and Efficient Algorithm. J. of Statistical Mechanics: Theory and Experiment, P10012 (2004)","DOI":"10.1088\/1742-5468\/2004\/10\/P10012"},{"key":"70_CR15","doi-asserted-by":"crossref","unstructured":"Duchon, P., Hanusse, N., Lebhar, E., Schabanel, N.: Could any graph be turned into a small world? Technical Report LIP RR-2004-61, ENS-Lyon (December 2004)","DOI":"10.1007\/11561927_46"},{"key":"70_CR16","volume-title":"Cluster Analysis","author":"B. Everitt","year":"2001","unstructured":"Everitt, B., Landau, S., Leese, M.: Cluster Analysis, 4th edn. Arnold, London (2001)","edition":"4"},{"key":"70_CR17","doi-asserted-by":"crossref","unstructured":"Feige, U., Hajiaghayi, M., Lee, J.: Improved approximation algorithms for minimum-weight vertex separators. In: 37th ACM Symposium on Theory of Computing, STOC (2005)","DOI":"10.1145\/1060590.1060674"},{"key":"70_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1007\/3-540-48224-5_62","volume-title":"Automata, Languages and Programming","author":"P. Fraigniaud","year":"2001","unstructured":"Fraigniaud, P., Gavoille, C.: Routing in trees. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol.\u00a02076, pp. 757\u2013772. Springer, Heidelberg (2001)"},{"key":"70_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/978-3-540-39989-6_15","volume-title":"17th Symposium on Distributed Computing (DISC)","author":"P. Fraigniaud","year":"2003","unstructured":"Fraigniaud, P., Gavoille, C.: End-to-end routing. In: DISC 2003. LNCS, vol.\u00a02848, pp. 211\u2013223. Springer, Heidelberg (2003)"},{"key":"70_CR20","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Gavoille, C., Paul, C.: Eclecticism shrinks even small worlds. In: 23rd ACM Symp. on Principles of Distributed Computing (PODC), pp. 169\u2013178 (2004)","DOI":"10.1145\/1011767.1011793"},{"key":"70_CR21","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., Paul, C., Peleg, D.: Approximate Distance Labeling Schemes. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol.\u00a02161, pp. 476\u2013487. Springer, Heidelberg (2001)"},{"key":"70_CR22","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M. Golumbic","year":"1980","unstructured":"Golumbic, M.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, New-York (1980)"},{"key":"70_CR23","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.: The Small-World Phenomenon: An Algorithmic Perspective. In: 32nd ACM Symp. on Theory of Computing (STOC), pp. 163\u2013170 (2000)","DOI":"10.1145\/335305.335325"},{"key":"70_CR24","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1038\/35022643","volume":"406","author":"J. Kleinberg","year":"2000","unstructured":"Kleinberg, J.: Navigation in a Small-World. Nature\u00a0406, 845 (2000)","journal-title":"Nature"},{"key":"70_CR25","unstructured":"Kleinberg, J.: Small-World Phenomena and the Dynamics of Information. In: 15th Neural Information Processing Systems, NIPS (2001)"},{"key":"70_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"894","DOI":"10.1007\/978-3-540-27836-8_75","volume-title":"31st International Colloquium on Automata, Languages and Programming (ICALP)","author":"E. Lebhar","year":"2004","unstructured":"Lebhar, E., Schabanel, N.: Searching for optimal paths in long-range contact networks. In: ICALP 2004. LNCS, vol.\u00a03142, pp. 894\u2013905. Springer, Heidelberg (2004)"},{"key":"70_CR27","doi-asserted-by":"crossref","unstructured":"Manku, G., Naor, M., Wieder, U.: Know Thy Neighbor\u2019s Neighbor: The Power of Lookahead in Randomized P2P Networks. In: 36th ACM Symp. on Theory of Computing, STOC (2004)","DOI":"10.1145\/1007352.1007368"},{"key":"70_CR28","doi-asserted-by":"crossref","unstructured":"Martel, C., Nguyen, V.: Analyzing Kleinberg\u2019s (and other) Small-world Models. In: 23rd ACM Symp. on Principles of Distributed Computing (PODC), pp. 178\u2013187 (2004)","DOI":"10.1145\/1011767.1011794"},{"key":"70_CR29","unstructured":"Martel, C., Nguyen, V.: Analyzing and Charaterizing Small-World Graphs. In: 16th ACM Symp. on Discrete Algorithms, SODA (2005)"},{"key":"70_CR30","doi-asserted-by":"crossref","unstructured":"Menczer, F.: Growing and Navigating the Small World Web by Local Content. In: Proc. Natl. Acad. Sci. USA, vol.\u00a099(22), pp. 14014\u201314019 (2002)","DOI":"10.1073\/pnas.212348399"},{"key":"70_CR31","doi-asserted-by":"crossref","unstructured":"Milgram, S.: The Small-World Problem. Psychology Today, 60\u201367 (1967)","DOI":"10.1037\/e400002009-005"},{"issue":"1","key":"70_CR32","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1145\/42267.42268","volume":"35","author":"N. Megiddo","year":"1988","unstructured":"Megiddo, N., Hakimi, S., Garey, M., Johnson, D., Papadimitriou, C.: The complexity of searching a graph. Journal of the ACM\u00a035(1), 18\u201344 (1988)","journal-title":"Journal of the ACM"},{"key":"70_CR33","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"},{"key":"70_CR34","doi-asserted-by":"publisher","first-page":"1302","DOI":"10.1126\/science.1070120","volume":"296","author":"D.J. Watts","year":"2002","unstructured":"Watts, D.J., Dodds, P.S., Newman, M.E.J.: Identity and Search in Social Networks. Science\u00a0296, 1302\u20131305 (2002)","journal-title":"Science"},{"key":"70_CR35","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"D. Watts","year":"1998","unstructured":"Watts, D., Strogatz, S.: Collective Dynamics of Small-World Networks. Nature\u00a0393, 440\u2013442 (1998)","journal-title":"Nature"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2013 ESA 2005"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11561071_70.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T19:50:50Z","timestamp":1605642650000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11561071_70"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540291183","9783540319511"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/11561071_70","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}