Min Hop and Foremost Paths in Interval Temporal Graphs
Anuj Jain, Sartaj K. Sahni · 2021 IEEE Symposium on Computers and Communications (ISCC) · 2021
We develop algorithms for foremost paths and min-hop paths in interval temporal graphs. These algorithms are benchmarked against the fastest algorithms known for foremost and min-hop paths in contact sequence temporal graphs. On our test data, our foremost path algorithm provides a speedup of up to 1800 over the fastest algorithm for contact sequence graphs; the speedup for our min-hop algorithm is up to 6700. We also demonstrate path problems that are NP-hard in the interval temporal graph model but polynomial in the contact sequence temporal graph model.