Close to linear space routing schemes
Tóm tắt
Let
$$G=(V,E)$$
be an unweighted undirected graph with n vertices and m edges, and let
$$k>2$$
be an integer. We present a routing scheme with a poly-logarithmic header size, that given a source s and a destination t at distance
$$\varDelta $$
from s, routes a message from s to t on a path whose length is
$$O(k\varDelta +m^{1/k})$$
. The total space used by our routing scheme is
$$mn^{O(1/\sqrt{\log n})}$$
, which is almost linear in the number of edges of the graph. We present also a routing scheme with
$$n^{O(1/\sqrt{\log n})}$$
header size, and the same stretch (up to constant factors). In this routing scheme, the routing table of every
$$v\in V$$
is at most
$$kn^{O(1/\sqrt{\log n})}deg(v)$$
, where deg(v) is the degree of v in G. Our results are obtained by combining a general technique of Bernstein (2009), that was presented in the context of dynamic graph algorithms, with several new ideas and observations.
Tài liệu tham khảo
Abraham, I., Gavoille, C.: On approximate distance labels and routing schemes with affine stretch. In: Peleg, D. (ed.) Distributed Computing-25th International Symposium, DISC 2011, Rome, Italy, September 20–22, 2011. Proceedings, pp. 404–415. Springer, Heidelberg (2011). doi:10.1007/978-3-642-24100-0. ISBN 978-3-642-24099-7
Agarwal, R., Godfrey, P.B.: Distance oracles for stretch less than 2. In: Khanna, S. (ed.) Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6–8, 2013, pp. 526–538. SIAM (2013). doi:10.1137/1.9781611973105.38. ISBN 978-1-61197-251-1
Agarwal, R., Godfrey, P.B., Har-Peled, S.: Approximate distance queries and compact routing in sparse graphs. In: INFOCOM 2011. 30th IEEE International Conference on Computer Communications, Joint Conference of the IEEE Computer and Communications Societies, 10–15 April 2011, Shanghai, China, pp. 1754–1762. IEEE (2011). doi:10.1109/INFCOM.2011.5934973. ISBN 978-1-4244-9921-2
Awerbuch, B., Bar-Noy, A., Linial, N., Peleg, D.: Improved routing strategies with succinct tables. J. Algorithms 11(3), 307–341 (1990)
Awerbuch, B., Peleg, D.: Routing with polynomial communication-space trade-off. SIAM J. Discret. Math. 5(2), 151–162 (1992)
Bernstein, A.: Fully dynamic (2 + epsilon) approximate all-pairs shortest paths with fast query and close to linear update time. In: 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25–27, 2009, Atlanta, Georgia, USA, pp. 693–702. IEEE Computer Society (2009). doi:10.1109/FOCS.2009.16. ISBN 978-0-7695-3850-1
Chechik, S.: Compact routing schemes with improved stretch. In: Fatourou. P., Taubenfeld, G. (eds.) ACM Symposium on Principles of Distributed Computing, PODC ’13, Montreal, QC, Canada, July 22–24, 2013, pp. 33–41. ACM (2013). doi:10.1145/2484239.2484268. ISBN 978-1-4503-2065-8
Chechik, S.: Approximate distance oracles with constant query time. In: Shmoys, D.B. (ed.) Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 – June 03, 2014, pp. 654–663. ACM (2014). doi:10.1145/2591796.2591801. ISBN 978-1-4503-2710-7
Cowen, L.: Compact routing with minimum stretch. J. Algorithms 38(1), 170–183 (2001)
Dor, D., Halperin, S., Zwick, U.: All-pairs almost shortest paths. SIAM J. Comput. 29(5), 1740–1759 (2000)
Eilam, T., Gavoille, C., Peleg, D.: Compact routing schemes with low stretch factor. J. Algorithms 46(2), 97–114 (2003)
Fraigniaud, P., Gavoille, C.: Routing in trees. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) Automata, Languages and Programming, 28th International Colloquium, ICALP 2001, Crete, Greece, July 8–12, 2001, Proceedings, pp. 757–772. Springer, Heidelberg (2001). doi:10.1007/3-540-48224-5_62. ISBN 3-540-42287-0
Gavoille, C., Sommer, C.: Sparse spanners vs. compact routing. In: Rajaraman, R., Friedhelm Meyer auf der Heide (eds.) SPAA 2011: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, San Jose, CA, USA, June 4–6, 2011 Co-located with FCRC 2011, pp. 225–234. ACM (2011). doi:10.1145/1989493.1989526. ISBN 978-1-4503-0743-7
Pǎtraşcu, M., Roditty, L.: Distance oracles beyond the Thorup–Zwick bound. SIAM J. Comput. 43(1), 300–311 (2014)
Pǎtraşcu, M., Roditty, L., Thorup, M.: A new infinity of distance oracles for sparse graphs. In: 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20–23, 2012, pp. 738–747. IEEE Computer Society (2012). doi:10.1109/FOCS.2012.44. ISBN 978-1-4673-4383-1
Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia (2000)
Peleg, D., Upfal, E.: A trade-off between space and efficiency for routing tables. J. ACM 36(3), 510–530 (1989)
Porat, E., Roditty, L.: Preprocess, set, query!. Algorithmica 67(4), 516–528 (2013)
Sommer, C., Verbin, E., Yu, W.: Distance oracles for sparse graphs. In: 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25–27, 2009, Atlanta, Georgia, USA, pp. 703–712. IEEE Computer Society (2009). doi:10.1109/FOCS.2009.27. ISBN 978-0-7695-3850-1
Thorup, M., Zwick, U.: Compact routing schemes. In: SPAA, pp. 1–10 (2001). doi:10.1145/378580.378581
Thorup, M., Zwick, U.: Approximate distance oracles. J. ACM 52(1), 1–24 (2005)
Thorup, M., Zwick, U.: Spanners and emulators with sublinear distance errors. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22–26, 2006, pp. 802–809. ACM Press, New York (2006). http://dl.acm.org/citation.cfm?id=1109557.1109645
Wulff-Nilsen, C.: Approximate distance oracles with improved preprocessing time. In: Rabani, Y. (ed.) Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17–19, 2012, pp. 202–208. SIAM (2012). doi:10.1137/1.9781611973099. ISBN 978-1-61197-210-8
Wulff-Nilsen, C.: Approximate distance oracles with improved query time. In: Encyclopedia of Algorithms (2015). doi:10.1007/978-3-642-27848-8. ISBN 978-3-642-27848-8