Path problems in temporal graphs
2014
Shortest path is a fundamental graph problem with numerous applications. However, the concept of classic shortest path is insufficient or even flawed in a temporal graph, as the temporal information determines the order of activities along any path. In this paper, we show the shortcomings of classic shortest path in a temporal graph, and study various concepts of "shortest" path for temporal graphs. Computing these temporal paths is challenging as subpaths of a "shortest" path may not be "shortest" in a temporal graph. We investigate properties of the temporal paths and propose efficient algorithms to compute them. We tested our algorithms on real world temporal graphs to verify their efficiency, and also show that temporal paths are essential for studying temporal graphs by comparing shortest paths in normal static graphs.
Keywords:
- Longest path problem
- Combinatorics
- Euclidean shortest path
- Yen's algorithm
- K shortest path routing
- Widest path problem
- Shortest path problem
- Shortest Path Faster Algorithm
- Discrete mathematics
- Mathematics
- Constrained Shortest Path First
- Computer science
- Data mining
- Canadian traveller problem
- Theoretical computer science
- Distance
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
23
References
145
Citations
NaN
KQI