Open AccessAn Algorithm for Determining Whether the Connectivity of a Graph is at Leastk
Author(s) -
Shimon Even
Publication year - 1975
Publication title -
siam journal on computing
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.533
H-Index - 122
eISSN - 1095-7111
pISSN - 0097-5397
DOI - 10.1137/0204034
Subject(s) - combinatorics , bounded function , undirected graph , algorithm , mathematics , graph , discrete mathematics , directed graph , graph algorithms , computer science , mathematical analysis
The algorithm presented in this paper is for testing whether the connectivity of a large graph of $n$ vertices is at least $k$. First the case of undirected graphs is discussed, and then it is shown that a variation of this algorithm works for directed graphs. The number of steps the algorithm requires, in case $k \sqrt{n}$, is bounded by $O(kn^{3})$.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom