Details

Autor(en) / Beteiligte

• Gheibi, Sanaz
• Banerjee, Tania
• Ranka, Sanjay
• Sahni, Sartaj

Titel

Path Algorithms for Contact Sequence Temporal Graphs

Ist Teil von

• Algorithms, 2024-04, Vol.17 (4), p.148

Ort / Verlag

Basel: MDPI AG

Erscheinungsjahr

2024

Link zum Volltext

Quelle

EZB Electronic Journals Library

Beschreibungen/Notizen

• This paper proposes a new time-respecting graph (TRG) representation for contact sequence temporal graphs. Our representation is more memory-efficient than previously proposed representations and has run-time advantages over the ordered sequence of edges (OSE) representation, which is faster than other known representations. While our proposed representation clearly outperforms the OSE representation for shallow neighborhood search problems, it is not evident that it does so for different problems. We demonstrate the competitiveness of our TRG representation for the single-source all-destinations fastest, min-hop, shortest, and foremost paths problems.