Improved Runtimes and Lower Bounds for Dual-Edge Failure Replacement Path Algorithms

Given a graph G and a fixed pair of nodes s and t, the Replacement Paths problem is to compute the new shortest distance from s to t when there are edge failures in G (i.e. those edges can no longer be used for any path). While there has been extensive research into the single-failure Replacement Paths problem, less progress has been made on multiple-failure algorithms. This thesis provides a new algorithm for the two-failure variant of the Replacement Paths problem, and shows a new combinatorial lower bound for the runtime of k-failure Replacement Paths for any positive integer k.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2021

Author dc:creator

• Woldeghebriel, Eyob W.

Advisor dc:contributor.advisor

• Williams, Virginia Vassilevska

Statement dc:rights

• In Copyright - Educational Use Permitted
• Copyright MIT

Licence dc:rights.uri

• http://rightsstatements.org/page/InC-EDU/1.0/

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/139098

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/139098