An Algorithm for Single-Source Shortest Paths Enumeration in Parameterized Weighted Graphs
| Autor: | Didier Lime, Loïg Jezequel, Bastien Sérée |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
050101 languages & linguistics
Computer science 05 social sciences Parameterized complexity 02 engineering and technology Parameter space Graph Valuation (logic) 0202 electrical engineering electronic engineering information engineering Enumeration 020201 artificial intelligence & image processing 0501 psychology and cognitive sciences Node (circuits) Algorithm MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Language and Automata Theory and Applications ISBN: 9783030681944 LATA |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|