Reinventing the wheel
Robert F. Cohen, Giuseppe Di Battista, Arkady Kanevsky, Roberto Tamassia · 1993
We show that, for any fixed k, there exists an optimal O(n)-space compact representation of a k-connected graph G with n vertices, such that one can determine in O(1) time whether two vertices areconnectedbyk+l vertex-dkjoint paths, or are separated by k vertices/edges.Previously, the existence of such compact representations was known only for k <3.1 Summary of ResultsA fundamental issue for the fault-tolerance and reliabilityofnetworksis determining the existence of multiple disjoint paths connecting two nodes.In this paper we investigate the problem of constructing a compact representation of a graph so that one can test quickly for the existence of such paths.