Connected reorientations of mixed multigraphs
Weigeng Shi, Ronald J. Juels · Networks · 1989
Abstract We study here the problem of reorienting the directed edges of mixed multigraphs so as to establish or preserve reachability, which may be destroyed by edge removal. We develop a linear time/space algorithm which tests whether reorienting designated directed edges can reestablish reachability, and which constructs such a reorientation whenever possible. We also develop a linear time/space algorithm which, when reachability has been destroyed by the removal of a single edge, optimally restores reachability through the reversal of selected edges. Finally, we show the reliability of a graph allowing reversals to be twice that of a graph for which reversals are not permitted.