EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
1981. A General Label Setting Algorithm for the Multiobjective Temporal Shortest Path Problem
Invited abstract in session WB-37: Discrete Multiobjective Optimization, stream Multiobjective Optimization.
Wednesday, 10:30-12:00Room: 33 (building: 306)
Authors (first author is the speaker)
| 1. | Clemens Thielen
|
| TUM Campus Straubing for Biotechnology and Sustainability, Technical University of Munich | |
| 2. | Cristina Bazgan
|
| Lamsade, Université Paris Dauphine | |
| 3. | Johannes Kager
|
| TUM Campus Straubing for Biotechnology and Sustainability, Technical University of Munich | |
| 4. | Daniel Vanderpooten
|
| LAMSADE, Université Paris Dauphine |
Abstract
Graphs in which the arc set changes over time (in discrete steps), are called temporal graphs. Given a directed temporal graph, a start node s, and a constant number of objectives, the task in the single-source multiobjective temporal shortest path problem consists of computing the set of nondominated images of temporal paths from s to every other node as well as one corresponding efficient path for each of these images. This problem generalizes both the multiobjective shortest path problem in static graphs and the singleobjective temporal shortest path problem.
This talk presents a general label setting algorithm for the single-source multiobjective temporal shortest path problem that can handle a large variety of different objectives. The only condition imposed on the objectives is a monotonicity property that generalizes the nonnegativity of the arc costs required for the well-known label setting algorithm for solving the static single-source shortest path problem in both the singleobjective and the multiobjective case. The worst-case running time of our algorithm is polynomial in the sum of the input size of the problem instance and the number of nondominated images, which means that it runs in polynomial time for all tractable versions of the problem.
To complement this result, we provide a complete classification into tractable and intractable problems for all single-source multiobjective temporal shortest path problems involving a large variety of objectives.
Keywords
- Multi-Objective Decision Making
- Graphs and Networks
- Algorithms
Status: accepted
Back to the list of papers