Terpene

thcscience_admin

In graph theory, a graph is k-edge-connected if it remains connected whenever fewer than k edges are removed.

The edge-connectivity of a graph is the largest k for which the graph is k-edge-connected.

Formal definition[edit]

Let G = (V, E) be an arbitrary graph. If subgraph G' = (V, E \setminus X) is connected for all X \subseteq E where |X| < k, then G is k-edge-connected.

Relation to minimum vertex degree[edit]

Minimum vertex degree gives a trivial upper bound on edge-connectivity. That is, if a graph G = (V, E) is k-edge-connected then it is necessary that k ≤ δ(G), where δ(G) is the minimum degree of any vertex v ∈ V. Obviously, deleting all edges incident to a vertex, v, would then disconnect v from the graph.

Computational aspects[edit]

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 n is the number of vertices in the graph, this simple algorithm would perform O(n^2) iterations of the Maximum flow problem, which can be solved in O(n^3) time. Hence the complexity of the simple algorithm described above is O(n^5) 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 O(n^4) and is sound since, if a cut of capacity less than k exists, it is bound to separate u from some other vertex. It can be further improved by an algorithm of Gabow that runs in worst case O(n^3) time. [1]

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 k\geq 2.[2]

See also[edit]

References[edit]

  1. ^ Harold N. Gabow. A matroid approach to finding edge connectivity and packing arborescences. J. Comput. Syst. Sci., 50(2):259–273, 1995.
  2. ^ M.R. Garey and D.S. Johnson. Computers and Intractability: a Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA, 1979.
source: https://web.archive.org/web/20150228002603/http://en.wikipedia.org/wiki/K-edge-connected_graph

Leave a Reply