Efficient Algorithms for Temporal Path Computation

Shortest path is a fundamental graph problem with numerous applications. However, the concept of classic shortest path is insufficient. In this paper, we study various concepts of "shortest" path in temporal graphs, called minimum temporal paths. Computing these minimum temporal paths is c...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on knowledge and data engineering 2016-11, Vol.28 (11), p.2927-2942
Main Authors: Huanhuan Wu, Cheng, James, Yiping Ke, Silu Huang, Yuzhen Huang, Hejun Wu
Format: Article
Language:English
Subjects:
Algorithm design and analysis
Clustering algorithms
Electronic mail
Heuristic algorithms
Message service
Parallel algorithms
parallel temporal path algorithms
Social network services
Temporal graphs
temporal path
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Shortest path is a fundamental graph problem with numerous applications. However, the concept of classic shortest path is insufficient. In this paper, we study various concepts of "shortest" path in temporal graphs, called minimum temporal paths. Computing these minimum temporal paths is challenging as subpaths of a "shortest" path may not be "shortest" in a temporal graph. We propose efficient algorithms to compute minimum temporal paths and verified their efficiency using large real-world temporal graphs.
ISSN:1041-4347
1558-2191
DOI:10.1109/TKDE.2016.2594065