Skip to content

Implement DigraphEdgeConnectivity and DigraphArcConnectivity #856

@reiniscirpons

Description

@reiniscirpons

A cut set of a digraph D is any set of edges whose removal disconnects it. The edge connectivity of D is the minimum size of any cut set of D. It would be nice to have an edge-based counterpart to VertexConnectivity (see #94 , if we ever get it merged :D). Using the DigraphMaximumFlow function, as a consequence of the max-flow min cut theorem, we could naively compute the edge connectivity as the minimum of Sum(DigraphMaximumFlow(D, u, v)[u]) where u, v range over all pairs of vertices of D, but this might be a bit too slow (because the maximum flow computation already takes O(V^2 * E) time, where V is the number of vertices and E is the number of edges).

The notes by Abdol-Hossein Esfahanian [1] have quite a detailed exposition detailing various optimizations on top of this to reduce the number of max-flow calls and also covers arc-connectivity (strong edge-connectivity), so could be a good starting point.

1: "Connectivity Algorithms" by Abdol-Hossein Esfahanian's
https://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf

Metadata

Metadata

Assignees

Labels

difficulty: 2A label for feature requests of medium difficultyfeature-requestA label for feature requestsgood-second-issueA label for issues that are good second time contributorshelp wantedA label for issues or PRs where help is wanted

Type

No type

Projects

Status

In Progress

Milestone

No milestone

Relationships

None yet

Development

No branches or pull requests

Issue actions