05919770

j

05919770 Bhandari, Ramesh The improved sliding shortest path algorithm. Congr. Numerantium 203, 175-192 (2010). 2010 Utilitas Mathematica Publishing Inc., Winnipeg EN shortest path algorithm weighted graph undirected sliding constrained rerouting network minimal edge weight changes optimization Summary: Given an undirected weighted graph, and a pair of vertices, $s$ and $t$, connected by the shortest path, and an edge pq not lying on the shortest path, what are the minimal edge weight changes required within the given graph to cause the shortest path between $s$ and $t$ to pass through edge $pq$? This is the type of problem often faced by network administrators in the telecommunication world. In this paper, we provide an improvement to an existing algorithm called the sliding shortest path algorithm to solve such a problem; the approach taken is one of including negative edge weight changes, not considered in the previous version. Allowing for negative edge weight changes then augments the parameter-search space, leading to fewer edge weight changes required to achieve the objective of rerouting network traffic over the path that includes edge $pq$. The algorithm easily extends to the case of constraining the shortest path to include a given vertex $p$, instead of an edge $pq$, by simply collapsing the edge $pq$ into a single vertex $p$.