Near Optimal Routing in a Small-World Network with Augmented Local Awareness

1. Albert, R., Jeong, H., Barabasi, A.-L.: The diameter of the World Wide Web. Nature 401(9), 130–131 (1999)

   Article  Google Scholar 

2. Aspnes, J., Diamadi, Z., Shah, G.: Fault-tolerant routing in peer-to-peer systems. In: Proceedings of PODC 2002, pp. 223–232 (2002)

   Google Scholar 

3. Barriére, L., Fraigniaud, P., Kranakis, E., Krizanc, D.: Efficient routing in networks with long range contacts. In: Welch, J.L. (ed.) DISC 2001. LNCS, vol. 2180, pp. 270–784. Springer, Heidelberg (2001)

   Chapter  Google Scholar 

4. Benjamini, I., Berger, N.: The Diameter of Long-Range Percolation Clusters on Finite Cycles. Random Structures and Algorithms 19(2), 102–111 (2001)

   Article  MATH  MathSciNet  Google Scholar 

5. Biskup, M.: Graph diameter in long-range percolation. Submitted to Electron. Comm. Probab (2004)

   Google Scholar 

6. Bollobás, B., Chung, F.R.K.: The Diameter of a cycle plus a random matching. SIAM Journal on Discrete Mathematics 1(3), 328–333 (1988)

   Article  MATH  MathSciNet  Google Scholar 

7. Coppersmith, D., Gamarnik, D., Sviridenko, M.: The diameter of a long-range percolation graph. Random Structures and Algorithms 21(1), 1–13 (2002)

   Article  MATH  MathSciNet  Google Scholar 

8. Dodds, P., Muhamad, R., Watts, D.: An experimental study of search in global social networks. Science 301, 827–829 (2003)

   Article  Google Scholar 

9. Kochen, M. (ed.): The small world, Ablex, Norwood (1989)

   Google Scholar 

10. Fraigniaud, P., Gavoille, C., Paul, C.: Eclecticism shrinks even small worlds. In: PODC 2004, pp. 169–178 (2004)

    Google Scholar 

11. Homan, C.M., Istrate, G.: Small worlds, locality, and flooding on landscapes. Research Report TR-2003-796, Department of Computer Science, University of Rochester, USA (2003)

    Google Scholar 

12. Kemper, D., Kleinberg, J., Demers, A.: Spatial gossip and resource location protocols. In: Proceedings of STOC, pp. 163–172 (2001)

    Google Scholar 

13. Kleinberg, J.: The Small-World Phenomenon: An Algorithmic Perspective. In: Proceedings of the 32nd ACM Symposium on Theory of Computing, pp. 163–170 (2000)

    Google Scholar 

14. Lebhar, E., Schabanel, N.: Almost optimal decentralized routing in long-range contact networks. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 894–905. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

15. Manku, G.S., Bawa, M., Raghavan, P.: Symphony: Distributed hashing in a small world. In: Proceedings of the 4th USENIX Symposium on Internet Technologies and Systems, pp. 127–140 (2003)

    Google Scholar 

16. Manku, G.S., Naor, M., Wieder, U.: Know thy neighbor’s neighbor: The power of lookahead in randomized p2p networks. In: Proceedings of STOC 2004, pp. 54–63 (2004)

    Google Scholar 

17. Martel, C., Nguyen, V.: Analyzing Kleinberg’s (and other) small-world models. In: PODC 2004, pp. 179–188 (2004)

    Google Scholar 

18. Milgram, S.: The small world problem. Psychology Today 61 (1967)

    Google Scholar 

19. Newman, M.E.J.: Models of the small world. J. Stat. Phys. 101 (2000)

    Google Scholar 

20. Nguyen, V., Martel, C.: Analyzing and Characterizing Small-World Graphs. In: SODA 2005 (2005)

    Google Scholar 

21. Watts, D., Strogatz, S.: Collective dynamics of small-world networks. Nature 393, 440–442 (1998)

    Article  Google Scholar 

22. Zhang, H., Goel, A., Govindan, R.: Using the small-world model to improve Freenet performance. In: Proceedings of IEEE INFOCOM 2002, pp. 1228–1237 (2002)

    Google Scholar 

23. Zeng, J., Hsu, W.-J.: Near Optimal Routing for Small-World Networks with Augmented Local Awareness (2005), Available at http://www.cais.ntu.edu.sg/~zjy

Download references