- Coordinator
- Ceske Vysoke Uceni Technicke V Praze, Czechia
- Runs
- 1 September 2026 to 31 August 2028
- Status
- Running
- EU funding
- €192k
- Total cost
- —
- Partners
- 1 organisations in 1 countries
- Type
- Marie Skłodowska-Curie Action
- Grant agreement
- 101334390
What the project is doing
In the project's own words, from its summary on CORDIS.
Pathfinding in graphs is one of the most fundamental problems in graph theory. Dijkstra’s algorithm for finding shortest paths between nodes has been a part of standard computer science curriculum for decades. However, in several applications in logistics and operations research, the desired path should satisfy some additional constraints, and thus cannot be found by a straightforward application of Dijkstra’s algorithm.
For example, on some crossroads turning right is not permitted, i.e. certain edges of the graph cannot appear as consecutive edges on the path. Another example occurs in pickup and delivery route planning, where each pick-up location needs to be visited beforethe corresponding destination. In other words, the ordering of the vertices on the path needs to respect a given partial order. The above scenarios might seem very different, but they share one key property that makes pathfinding difficult.
Namely, Dijkstra’s algorithm relies on triangle inequality, which does not hold in the above cases. The aim of this project is to design novel algorithms that overcome this obstacle and to conduct a systematic study on different variants of the pathfinding problem with traversal constraints. To achieve this, we will employ parameterized complexity tools, which enable us to study the complexity of problems with respect to multiple parameters describing the input and output data.
Topics
Who is involved
| Organisation | City | Country | Role |
|---|---|---|---|
| Ceske Vysoke Uceni Technicke V Praze | Praha | Czechia | Coordinator |
Source: CORDIS, European Commission. Data of 5 Nov 2026, reused under the Commission's reuse policy. View on CORDIS · Grant DOI