Restricted shortest path in temporal graphs

The restricted shortest path (RSP) problem on directed networks is a well-studied problem, and has a large number of applications such as in Quality of Service routing. The problem is known to be NP-hard. In certain cases, however, the network is not static i.e., edge parameters vary over time. In light of this, we extend the RSP problem for general networks to that for temporal networks. We present several exact algorithms for this problem, one of which uses heuristics, and is similar to the A∗ algorithm. We experimentally evaluate these algorithms by simulating them on both existing temporal networks, and synthetic ones. Furthermore, based on one of the pseudo-polynomial exact algorithms, we derive a fully polynomial time approximation scheme