Incrementing bipartite digraph edge-connectivity
The authors solve the problem to increase the edge connectivity of a bipartite digraph by adding the smallest number of edges that keep the graph bipartite. This problem is motivated from statics where a square grid framework should be reinforced by cables. Actually, the more general problem of covering a crossing family of sets with the smallest number of directed edges is solved, where each edge must join the blocks of a given bipartition of the elements. The smallest number of new edges is given by a min-max formula which has six infinite families of exceptional cases (blockers). Moreover, two other incrementation problems with a similar structure are solved: one concerns a problem on network flows which has three families of blockers. The other concerns spanning arborescences that has five families of blockers. For increasing the edge connectivity of a bipartite digraph with \(n\) vertices, \(m\) edges and the target connectivity \(k\), which keeps bipartiteness, the authors state an algorithm of time complexity \(O(km \log n)\) in the unweighted case and of \(O(nm \log (n^2/m))\) in the weighted case.
- Increasing digraph arc-connectivity by arc addition, reversal and complement
- Augmenting weighted graphs to establish directed point-to-point connectivity
- Making bipartite graphs DM-irreducible
- Optimal algorithm for converting an acyclic digraph to a cluster
- How to Secure Matchings against Edge Failures
- Smallest Bipartite Bridge-Connectivity Augmentation (Extended Abstract)
- Bipartition constrained edge-splitting in directed graphs
- Augmenting the rigidity of a graph in \(\mathbb R^{2}\)
This page was built for publication: Incrementing bipartite digraph edge-connectivity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1592842)
