Visualizing, Finding and Packing Dijoins

F.B. Shepherd and A. Vetta

Chapter Chapter 8 in Graph Theory and Combinatorial Optimization, 2005, pp 219-254 from Springer

Abstract: Abstract We consider the probleni of making a directed graph strongly connected. To achieve this, we are allowed for assorted costs to add the reverse of any arc. A successful set of arcs, called a dijoin, must intersect every directed cut. Lucchesi and Younger gave a min-max theorem for the problem of finding a mininmum cost dijoin. Less understood is the extent to which dijoins pack. One difliculty is that dijoins are not as easily visualized as other combinatorial objects such as matchings, trees or flows. We give two results which act as visual certificates for dijoins. One of these, called a lobe decomposition, resembles Whitney's ear decomposition for 2-connected graphs. The decomposition leads to a natural optimality condition for dijoins. Based on this, we give a simple description of Frank's primal-dual algorithm to find a minimum dijoin. Our implementation is purely primal and only uses greedy tree growing procedures. Its runtime is O(n 2 m), matching the best known, due to Gabow. We then consider the function f(k) which is the maximurn value such that every weighted directed graph whose minimum weight of a directed cut is at least k, admits a weighted packing of f(k) dijoins (a weighted packing means that the number dijoins containing an arc is at most its weight). We ask whether f(k) approaches infinity. It is not yet known whether f(k 0) ≥ 2 for sorne constant k 0. We consider a concept of skew submodular flow polyhedra and show that this dijoin- pair question reduces to finding conditions on when their integer hulls are non-empty. We also show that for any k, there exists a half-integral dijoin packing of size k/2.

Keywords: Complete Cycle; Directed Cycle; Submodular Function; Negative Cycle; Negative Cost (search for similar items in EconPapers)
Date: 2005
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:sprchp:978-0-387-25592-7_8

Ordering information: This item can be ordered from
http://www.springer.com/9780387255927

DOI: 10.1007/0-387-25592-3_8

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().