Connectivity and cut algorithms
Algorithms for finding k-edge-augmentations
A k-edge-augmentation is a set of edges, that once added to a graph, ensures that the graph is k-edge-connected; i.e. the graph cannot be disconnected unless k or more edges are removed. Typically, the goal is to find the augmentation with minimum weight. In general, it is not guaranteed that a k-edge-augmentation exists.
- algorithms for finding k-edge-connected components
- algorithms for determening edge connectivity.
||Finds set of edges to k-edge-connect G.|
||Tests to see if a graph is k-edge-connected.|
||Tests to see if an edge in a graph is locally k-edge-connected.|
Algorithms for finding k-edge-connected components and subgraphs.
A k-edge-connected component (k-edge-cc) is a maximal set of nodes in G, such that all pairs of node have an edge-connectivity of at least k.
A k-edge-connected subgraph (k-edge-subgraph) is a maximal set of nodes in G, such that the subgraph of G defined by the nodes has an edge-connectivity at least k.
||Generates nodes in each maximal k-edge-connected component in G.|
||Generates nodes in each maximal k-edge-connected subgraph in G.|
||Finds all bridge-connected components G.|
||A simple algorithm to find all k-edge-connected components in a graph.|
Moody and White algorithm for k-components
||Returns the k-component structure of a graph G.|
Kanevsky all minimum node k cutsets algorithm.
||Returns all minimum k cutsets of an undirected graph G.|
Flow-based disjoint paths¶
Flow based node and edge disjoint paths.
||Returns the edges disjoint paths between source and target.|
||Computes node disjoint paths between source and target.|
Flow based connectivity algorithms
||Returns the average connectivity of a graph G.|
||Compute node connectivity between all pairs of nodes of G.|
||Returns the edge connectivity of the graph or digraph G.|
||Returns local edge connectivity for nodes s and t in G.|
||Computes local node connectivity for nodes s and t.|
||Returns node connectivity for a graph or digraph G.|
Flow-based Minimum Cuts¶
Flow based cut algorithms
||Returns a set of edges of minimum cardinality that disconnects G.|
||Returns a set of nodes of minimum cardinality that disconnects G.|
||Returns the edges of the cut-set of a minimum (s, t)-cut.|
||Returns a set of nodes of minimum cardinality that disconnect source from target in G.|
Stoer-Wagner minimum cut¶
Stoer-Wagner minimum cut algorithm.
||Returns the weighted minimum edge cut using the Stoer-Wagner algorithm.|