Medial Axis Based Routing Has Constant Load Balancing Factor

1. Andrews, M., Zhang, L.: Hardness of the undirected congestion minimization problem. SIAM Journal on Computing 37(1), 112–131 (2007)

   Article  MathSciNet  MATH  Google Scholar 

2. Attali, D., Boissonnat, J.-D., Edelsbrunner, H.: Stability and computation of the medial axis — a state-of-the-art report. In: Mathematical Foundations of Scientific Visualization, Computer Graphics, and Massive Data Exploration. Springer (2004)

   Google Scholar 

3. Bruck, J., Gao, J., Jiang, A.: MAP: Medial axis based geometric routing in sensor networks. Wireless Networks 13(6), 835–853 (2007)

   Article  Google Scholar 

4. Chekuri, C., Khanna, S., Shepherd, F.B.: An \(o(\sqrt{n})\)-approximation for EDP in undirected graphs and directed acyclic graphs. Theory of Computing 2, 137–146 (2006)

   Article  MathSciNet  MATH  Google Scholar 

5. Chuzhoy, J., Khanna, S.: New hardness results for undirected edge-disjoint paths. Manuscript (2005)

   Google Scholar 

6. Gao, J., Zhang, L.: Well-separated pair decomposition for the unit-disk graph metric and its applications. In: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, STOC 2003, pp. 483–492. ACM, New York (2003)

   Chapter  Google Scholar 

7. Gao, J., Zhang, L.: Load balanced short path routing in wireless networks. In: IEEE InfoCom, vol. 23, pp. 1099–1108 (March 2004)

   Google Scholar 

8. Goswami, M., Ni, C.-C., Ban, X., Gao, J., Gu, D.X., Pingali, V.: Load balanced short path routing in large-scale wireless networks using area-preserving maps. In: Proceedings of the 15th ACM International Symposium on Mobile Ad Hoc Networking and Computing (Mobihoc 2014), pp. 63–72 (August 2014)

   Google Scholar 

9. Karp, R.M.: Reducibility Among Combinatorial Problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum Press (1972)

   Google Scholar 

10. Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM Journal on Applied Mathematics 36(2), 177–189 (1979)

    Article  MathSciNet  MATH  Google Scholar 

11. Mei, A., Stefa, J.: Routing in outer space: fair traffic load in multi-hop wireless networks. In: MobiHoc 2008: Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing, pp. 23–32. ACM, New York (2008)

    Google Scholar 

12. Popa, L., Rostamizadeh, A., Karp, R., Papadimitriou, C., Stoica, I.: Balancing traffic load in wireless networks with curveball routing. In: MobiHoc 2007: Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing, pp. 170–179 (2007)

    Google Scholar 

13. Raghavan, P.: Probabilistic construction of deterministic algorithms: approximating packing integer programs. J. Comp. and System Sciences, 130–143 (1988)

    Google Scholar 

14. Raghavan, P., Thompson, C.D.: Provably good routing in graphs: regular arrays. In: Proceedings of the 17th Annual ACM Symposium on Theory of Computing, pp. 79–87 (1985)

    Google Scholar 

15. Sarkar, R., Zeng, W., Gao, J., Gu, X.D.: Covering space for in-network sensor data storage. In: Proc. of the 9th International Symposium on Information Processing in Sensor Networks (IPSN 2010), pp. 232–243 (April 2010)

    Google Scholar 

16. Yu, X., Ban, X., Sarkar, R., Zeng, W., Gu, X.D., Gao, J.: Spherical representation and polyhedron routing for load balancing in wireless sensor networks. In: Proc. of 30th Annual IEEE Conference on Computer Communications (INFOCOM 2011), pp. 612–615 (April 2011)

    Google Scholar 

Download references