1. Abraham, I., Chechik, S., Gavoille, C.: Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels. In: Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, STOC 2012, pp. 1199–1218. ACM, New York (2012).http://doi.acm.org/10.1145/2213977.2214084

2. Abraham, I., Chechik, S., Krinninger, S.: Fully dynamic all-pairs shortest paths with worst-case update-time revisited. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 440–452. SIAM (2017)

   Google Scholar 

3. Abraham, I., Chechik, S., Talwar, K.: Fully dynamic all-pairs shortest paths: breaking the\(o(n)\) barrier. In: APPROX-RANDOM, pp. 1–16 (2014)

   Google Scholar 

4. Arlazarov, V.L., Dinic, E.A., Kronrod, M.A., Faradžev, I.A.: On economical construction of the transitive closure of a directed graph. Soviet Mathematics-Doklady11(5), 1209–1210 (1970)

   MATH  Google Scholar 

5. Bender, M.A., Farach-Colton, M.: The level ancestor problem simplified. Theoretical Computer Science321(1), 5–12 (2004)

   Article MathSciNet MATH  Google Scholar 

6. Bernstein, A., Karger, D.: Improved distance sensitivity oracles via random sampling. In: Proceedings 19th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 34–43 (2008)

   Google Scholar 

7. Bernstein, A., Karger, D.: A nearly optimal oracle for avoiding failed vertices and edges. In: Proceedings 41st Annual ACM Symposium on Theory of Computing (STOC), pp. 101–110 (2009)

   Google Scholar 

8. Chechik, S., Langberg, M., Peleg, D., Roditty, L.: f-sensitivity distance oracles and routing schemes. Algorithmica63(4), 861–882 (2012).http://dx.doi.org/10.1007/s00453-011-9543-0

   Article MathSciNet MATH  Google Scholar 

9. Demetrescu, C., Italiano, G.F.: A new approach to dynamic all pairs shortest paths. J. ACM51(6), 968–992 (2004)

   Article MathSciNet MATH  Google Scholar 

10. Demetrescu, C., Thorup, M., Chowdhury, R.A., Ramachandran, V.: Oracles for distances avoiding a failed node or link. SIAM J. Comput.37(5), 1299–1318 (2008)

    Article MathSciNet MATH  Google Scholar 

11. Demetrescu, C., Italiano, G.F.: Fully dynamic all pairs shortest paths with real edge weights. J. Comput. Syst. Sci.72(5), 813–837 (2006).http://dx.doi.org/10.1016/j.jcss.2005.05.005

    Article MathSciNet MATH  Google Scholar 

12. Demetrescu, C., Thorup, M.: Oracles for distances avoiding a link-failure. In: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2002, pp. 838–843. Society for Industrial and Applied Mathematics, Philadelphia (2002).http://dl.acm.org/citation.cfm?id=545381.545490

13. Duan, R., Pettie, S.: Dual-failure distance and connectivity oracles. In: Proceedings 20th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 506–515 (2009)

    Google Scholar 

14. Fredman, M.L., Willard, D.E.: Surpassing the information-theoretic bound with fusion trees. J. Comput. Syst. Sci.47(3), 424–436 (1993)

    Article MathSciNet MATH  Google Scholar 

15. Grandoni, F., Williams, V.V.: Improved distance sensitivity oracles via fast single-source replacement paths. In: FOCS, pp. 748–757. IEEE Computer Society (2012).http://dblp.uni-trier.de/db/conf/focs/focs2012.html#GrandoniW12

16. Henzinger, M., Krinninger, S., Nanongkai, D.: Dynamic approximate all-pairs shortest paths: breaking the o(mn) barrier and derandomization. In: 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, Proceedings. IEEE, Los Alamitos, October 2013.http://eprints.cs.univie.ac.at/3747/

17. Henzinger, M., Krinninger, S., Nanongkai, D.: Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs. In: 46th ACM Symposium on Theory of Computing (STOC 2014), June 2014.http://eprints.cs.univie.ac.at/4042/

18. Henzinger, M., Krinninger, S., Nanongkai, D.: A subquadratic-time algorithm for decremental single-source shortest paths. In: SODA 2014. SIAM, Philadelphia, January 2014.http://eprints.cs.univie.ac.at/3785/

19. Hershberger, J., Suri, S.: Vickrey prices and shortest paths: what is an edge worth?. In: Proceedings 42nd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 252–259 (2001). erratum, Proceedings of 43rd FOCS, p. 809, 2002

    Google Scholar 

20. Khanna, N., Baswana, S.: Approximate shortest paths avoiding a failed vertex: optimal size data structures for unweighted graphs. In: 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, March 4–6, 2010, Nancy, France, pp. 513–524 (2010).http://dx.doi.org/10.4230/LIPIcs.STACS.2010.2481

21. Patrascu, M., Roditty, L.: Distance oracles beyond the thorup-zwick bound. In: Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010, pp. 815–823. IEEE Computer Society, Washington, DC (2010).http://dx.doi.org/10.1109/FOCS.2010.83

22. Thorup, M.: Worst-case update times for fully-dynamic all-pairs shortest paths. In: Proceedings 37th ACM Symposium on Theory of Computing (STOC), pp. 112–119 (2005)

    Google Scholar 

Download references