An Algorithm for Vertex-pair Connectivity |
| |
| Authors: | By I. T. FRISCH |
| |
| Affiliation: | Electronics Research Laboratory and Department of Electrical Engineering and Computer Sciences , University of California , Berkeley, California |
| |
| Abstract: | An algorithm is developed for finding the minimum number of vertices ω s,t whose removal from a directed graph G breaks all directed paths from a given vertex s to a given vertex t. The algorithm is performed on G without any modification of its structure and entails examining each vertex at most r times with 2ω s,t ≥ r and, in practice, almost always with ω s,t ≥ r. |
| |
| Keywords: | |
|
|
