Computational Aspects
There is a polynomial-time algorithm to determine the largest k for which a graph G is k-edge-connected. A simple algorithm would, for every pair (u,v), determine the maximum flow from u to v with the capacity of all edges in G set to 1 for both directions. A graph is k-edge-connected if and only if the maximum flow from u to v is at least k for any pair (u,v), so k is the least u-v-flow among all (u,v).
If V is the number of vertices in the graph, this simple algorithm would perform iterations of the Maximum flow problem, which can be solved in time. Hence the complexity of the simple algorithm described above is in total.
An improved algorithm will solve the maximum flow problem for every pair (u,v) where u is arbitrarily fixed while v varies over all vertices. This reduces the complexity to and is sound since, if a cut of capacity less than k exists, it is bound to separate u from some other vertex.
A related problem: finding the minimum k-edge-connected subgraph of G (that is: select as few as possible edges in G that your selection is k-edge-connected) is NP-hard for .
Read more about this topic: K-edge-connected Graph
Famous quotes containing the word aspects:
“Grammar is a tricky, inconsistent thing. Being the backbone of speech and writing, it should, we think, be eminently logical, make perfect sense, like the human skeleton. But, of course, the skeleton is arbitrary, too. Why twelve pairs of ribs rather than eleven or thirteen? Why thirty-two teeth? It has something to do with evolution and functionalism—but only sometimes, not always. So there are aspects of grammar that make good, logical sense, and others that do not.”
—John Simon (b. 1925)