A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes | SpringerLink
Skip to main content
Springer Nature Link
Log in

A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes

  • Conference paper
Graph-Theoretic Concepts in Computer Science (WG 2008)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5344))

Included in the following conference series:

Abstract

We generalize the linear-time shortest-paths algorithm for planar graphs with nonnegative edge-weights of Henzinger et al. (1994) to work for any proper minor-closed class of graphs. We argue that their algorithm can not be adapted by standard methods to all proper minor-closed classes. By using recent deep results in graph minor theory, we show how to construct an appropriate recursive division in linear time for any graph excluding a fixed minor and how to transform the graph and its division afterwards, so that it has maximum degree three. Based on such a division, the original framework of Henzinger et al. can be applied. Afterwards, we show that using this algorithm, one can implement Mehlhorn’s (1988) 2-approximation algorithm for the Steiner tree problem in linear time on these graph classes.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Dijkstra, E.: A note on two problems in connexion with graphs. Numerische Mathematik 1, 269–271 (1959)

    Article  MathSciNet  MATH  Google Scholar 

  2. Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM 34(3), 596–615 (1987)

    Article  MathSciNet  Google Scholar 

  3. Pettie, S., Ramachandran, V.: A shortest path algorithm for real-weighted undirected graphs. SIAM Journal on Computing 34(6), 1398–1431 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  4. Goldberg, A.V.: A simple shortest path algorithm with linear average time. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol. 2161, pp. 230–241. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  5. Thorup, M.: Undirected single-source shortest paths with positive integer weights in linear time. Journal of the ACM 46(3), 362–394 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  6. Hagerup, T.: Improved shortest paths on the word RAM. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol. 1853, pp. 61–72. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

  7. Henzinger, M.R., Klein, P.N., Rao, S., Subramanian, S.: Faster shortest-path algorithms for planar graphs. Journal of Computer and System Sciences 55(1), 3–23 (1997); STOC 1994: Proceedings of the 26th Annual ACM Symposium on Theory of Computing, pp. 27–37. ACM Press, New York

    Article  MathSciNet  MATH  Google Scholar 

  8. Frederickson, G.N.: Data structures for on-line updating of minimum spanning trees, with applications. SIAM Journal on Computing 14(4), 781–798 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  9. Frederickson, G.N.: Fast algorithms for shortest paths in planar graphs, with applications. SIAM Journal on Computing 16(6), 1004–1022 (1987)

    Article  MathSciNet  MATH  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. Reed, B., Wood, D.R.: Fast separation in a graph with an excluded minor. In: EuroComb 2005: 2005 European Conference on Combinatorics, Graph Theory and Applications. DMTCS Proceeding. Discrete Mathematics and Theoretical Computer Science, vol. AE, pp. 45–50 (2005)

    Google Scholar 

  12. Alon, N., Seymour, P., Thomas, R.: A separator theorem for nonplanar graphs. Journal of the American Mathematical Society 3(4), 801–808 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  13. Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85–103. Plenum Press (1972)

    Google Scholar 

  14. Robins, G., Zelikovsky, A.: Improved Steiner tree approximation in graphs. In: SODA 2000: Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 770–779 (2000)

    Google Scholar 

  15. Chlebík, M., Chlebíková, J.: Approximation hardness of the Steiner tree problem on graphs. In: Penttonen, M., Schmidt, E.M. (eds.) SWAT 2002. LNCS, vol. 2368, pp. 170–179. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  16. Choukhmane, E.A.: Une heuristique pour le problème de l’arbre de Steiner. Recherche Opèrationelle 12, 207–212 (1978)

    MathSciNet  MATH  Google Scholar 

  17. Plesnik, J.: A bound for the Steiner problem in graphs. Mathematica Slovaca 31, 155–163 (1981)

    MathSciNet  MATH  Google Scholar 

  18. Mehlhorn, K.: A faster approximation algorithm for the Steiner problem in graphs. Information Processing Letters 27, 125–128 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  19. Mares, M.: Two linear time algorithms for MST on minor closed graph classes. Archivum Mathematicum 40(3), 315–320 (2004)

    MathSciNet  MATH  Google Scholar 

  20. Robertson, N., Seymour, P.D.: Graph minors. XX. Wagner’s conjecture. Journal of Combinatorial Theory Series B 92(2), 325–357 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  21. Mader, W.: Homomorphieeigenschaften und mittlere Kantendichte von Graphen. Mathematische Annalen 174, 265–268 (1967)

    Article  MathSciNet  MATH  Google Scholar 

  22. Robertson, N., Seymour, P.: Graph minors. XVI. Excluding a non-planar graph. Journal of Combinatorial Theory Series B 89(1), 43–76 (2003)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Technische Universität Darmstadt, Darmstadt, Germany

    Siamak Tazari

  2. Martin-Luther Universität Halle-Wittenberg, Halle (Saale), Germany

    Matthias Müller-Hannemann

Authors
  1. Siamak Tazari
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Matthias Müller-Hannemann
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, Durham University, South Road, DH1 3LE, Durham, UK

    Hajo Broersma , Tom Friedetzky  & Daniel Paulusma ,  & 

  2. Department of Computer Science, University of Leicester, University Road, LE1 7RH, Leicester, UK

    Thomas Erlebach

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Tazari, S., Müller-Hannemann, M. (2008). A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds) Graph-Theoretic Concepts in Computer Science. WG 2008. Lecture Notes in Computer Science, vol 5344. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-92248-3_32

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-92248-3_32

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-92247-6

  • Online ISBN: 978-3-540-92248-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics