A Polynomial Time Algorithm for Almost Optimal Vertex Fault Tolerant Spanners

02/26/2020
by   Udit Agarwal, et al.
0

We present the first polynomial time algorithm for the f vertex fault tolerant spanner problem, which achieves almost optimal spanner size. Our algorithm for constructing f vertex fault tolerant spanner takes O(k· n· m^2 · W) time, where W is the maximum edge weight, and constructs a spanner of size O(n^1+1/kf^1-1/k· (log n)^1-1/k). Our spanner has almost optimal size and is at most a log n factor away from the upper bound on the worst-case size. Prior to this work, no other polynomial time algorithm was known for constructing f vertex fault tolerant spanner with optimal size. Our algorithm is based on first greedily constructing a hitting set for the collection of paths of weight at most k · w(u,v) between the endpoints u and v of an edge (u,v) and then using this set to decide whether the edge (u,v) needs to be added to the growing spanner.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset