Skip to main content
Top

2021 | OriginalPaper | Chapter

An Algorithm for Single-Source Shortest Paths Enumeration in Parameterized Weighted Graphs

Authors : Bastien Sérée, Loïg Jezequel, Didier Lime

Published in: Language and Automata Theory and Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We consider weighted graphs with parameterized weights and we propose an algorithm that, given such a graph and a source node, builds a collection of trees, each one describing the shortest paths from the source to all the other nodes of the graph for a particular zone of the parameter space. Moreover, the union of these zones covers the full parameter space: given any valuation of the parameters, one of the trees gives the shortest paths from the source to all the other nodes of the graph when the weights are computed using this valuation.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
1.
go back to reference Alur, R., Henzinger, T.A., Vardi, M.Y.: Parametric real-time reasoning. In: ACM Symposium on Theory of Computing, pp. 592–601 (1993) Alur, R., Henzinger, T.A., Vardi, M.Y.: Parametric real-time reasoning. In: ACM Symposium on Theory of Computing, pp. 592–601 (1993)
3.
go back to reference André, É., Lime, D., Ramparison, M., Stoelinga, M.: Parametric analyses of attack-fault trees. In: Keller, J., Penczek, W. (eds.) 19th International Conference on Application of Concurrency to System Design (ACSD 2019), Aachen, Germany. IEEE Computer Society, June 2019 André, É., Lime, D., Ramparison, M., Stoelinga, M.: Parametric analyses of attack-fault trees. In: Keller, J., Penczek, W. (eds.) 19th International Conference on Application of Concurrency to System Design (ACSD 2019), Aachen, Germany. IEEE Computer Society, June 2019
4.
go back to reference Bundala, D., Ouaknine, J.: On parametric timed automata and one-counter machines. Inf. Comput. 253, 272–303 (2017)MathSciNetCrossRef Bundala, D., Ouaknine, J.: On parametric timed automata and one-counter machines. Inf. Comput. 253, 272–303 (2017)MathSciNetCrossRef
5.
go back to reference Chakraborty, S., Fischer, E., Lachish, O., Yuster, R.: Two-phase algorithms for the parametric shortest path problem. In: Marion, J.-Y., Schwentick, T. (eds.) 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, Nancy, France, 4–6 March 2010, vol. 5 of LIPIcs, pp. 167–178. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010) Chakraborty, S., Fischer, E., Lachish, O., Yuster, R.: Two-phase algorithms for the parametric shortest path problem. In: Marion, J.-Y., Schwentick, T. (eds.) 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, Nancy, France, 4–6 March 2010, vol. 5 of LIPIcs, pp. 167–178. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2010)
6.
go back to reference Karp, R.M., Orlin, J.B.: Parametric shortest path algorithms with an application to cyclic staffing. Discrete Appl. Math. 3(1), 37–45 (1981)MathSciNetCrossRef Karp, R.M., Orlin, J.B.: Parametric shortest path algorithms with an application to cyclic staffing. Discrete Appl. Math. 3(1), 37–45 (1981)MathSciNetCrossRef
8.
go back to reference Young, N., Tarjan, R., Orlin, J.: Faster parametric shortest path and minimum balance algorithms. Networks 21(2), 205–221 (1991)MathSciNetCrossRef Young, N., Tarjan, R., Orlin, J.: Faster parametric shortest path and minimum balance algorithms. Networks 21(2), 205–221 (1991)MathSciNetCrossRef
Metadata
Title
An Algorithm for Single-Source Shortest Paths Enumeration in Parameterized Weighted Graphs
Authors
Bastien Sérée
Loïg Jezequel
Didier Lime
Copyright Year
2021
DOI
https://doi.org/10.1007/978-3-030-68195-1_22

Premium Partner