An Effective Data Structure for Contact Sequence Temporal Graphs
Sanaz Gheibi, Tania Banerjee, Sanjay Ranka, Sartaj K. Sahni · 2021 IEEE Symposium on Computers and Communications (ISCC) · 2021
We propose a new time-respecting data structure (TRG) for contact sequence temporal graphs that is more memory efficient than previously proposed TRGs. Our new TRG alters the balance between TRG structures and the ordered sequence of edges (OSE) data structure. While TRG structures have an obvious performance advantage over OSE for problems that can be solved via a shallow neighborhood search, previous research has shown that single-source all-destinations problems are more effectively solved using OSE. The competitiveness of our TRG structure for this class of problems is demonstrated for the single-source all-destinations fastest paths and min-hop paths problems. Our TRG structure retains the advantage that other similar structures have over OSE for shallow neighborhood search problems.