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 Pa...

全面介绍

书目详细资料
主要作者: Woldeghebriel, Eyob W.
其他作者: Williams, Virginia Vassilevska
格式: Thesis
出版: Massachusetts Institute of Technology 2022
在线阅读:https://hdl.handle.net/1721.1/139098