Incrementing Bipartite Digraph Edge-Connectivity

Harold N. Gabow () and Tibor Jordán ()
Additional contact information
Harold N. Gabow: University of Colorado at Boulder
Tibor Jordán: Eötvös University

Journal of Combinatorial Optimization, 2000, vol. 4, issue 4, No 4, 449-486

Abstract: Abstract This paper solves the problem of increasing the edge-connectivity of a bipartite digraph by adding the smallest number of new edges that preserve bipartiteness. A natural application arises when we wish to reinforce a 2-dimensional square grid framework with cables. We actually solve the more general problem of covering a crossing family of sets with the smallest number of directed edges, where each new 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 that has six infinite families of exceptional cases. We discuss a problem on network flows whose solution has a similar formula with three infinite families of exceptional cases. We also discuss a problem on arborescences whose solution has five infinite families of exceptions. We give an algorithm that increases the edge-connectivity of a bipartite digraph in the same time as the best-known algorithm for the problem without the bipartite constraint: O(km log n) for unweighted digraphs and O(nm log (n 2/m)) for weighted digraphs, where n, m and k are the number of vertices and edges of the given graph and the target connectivity, respectively.

Keywords: graph algorithms; connectivity augmentation; min-max theorems; crossing family; square grid framework; rigidity (search for similar items in EconPapers)
Date: 2000
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1023/A:1009885511650 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:4:y:2000:i:4:d:10.1023_a:1009885511650

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1009885511650

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().