Near Optimal Sized Weight Tolerant Subgraph for Single Source Shortest Path

Diptarka Chakraborty, Debarati Das

In this paper we address the problem of computing a sparse subgraph of a weighted directed graph such that the exact distances from a designated source vertex to all other vertices…