Two-phase algorithms for the parametric shortest path problem

Eldar Fischer, Oded Lachish, Raphael Yuster

A {\em parametric weighted graph} is a graph whose edges are labeled with continuous real functions of a single common variable. For any instantiation of the variable, one obtains…