Mathematics – Combinatorics
Scientific paper
2003-04-21
Mathematical Programming, 100, No 3, 2004, 537-568
Mathematics
Combinatorics
35 pages, 3 figures, to appear in Mathematical Programming, minor stylistic corrections and shortenings to the original versio
Scientific paper
The maximum integer skew-symmetric flow problem (MSFP) generalizes both the maximum flow and maximum matching problems. It was introduced by Tutte in terms of self-conjugate flows in antisymmetrical digraphs. He showed that for these objects there are natural analogs of classical theoretical results on usual network flows, such as the flow decomposition, augmenting path, and max-flow min-cut theorems. We give unified and shorter proofs for those theoretical results. We then extend to MSFP the shortest augmenting path method of Edmonds and Karp and the blocking flow method of Dinits, obtaining algorithms with similar time bounds in general case. Moreover, in the cases of unit arc capacities and unit ``node capacities'' the blocking skew-symmetric flow algorithm has time bounds similar to those established in Even and Tarjan (1975) and Karzanov (1973) for Dinits' algorithm. In particular, this implies an algorithm for finding a maximum matching in a nonbipartite graph in $O(\sqrt{n}m)$ time, which matches the time bound for the algorithm of Micali and Vazirani. Finally, extending a clique compression technique of Feder and Motwani to particular skew-symmetric graphs, we speed up the implied maximum matching algorithm to run in $O(\sqrt{n}m\log(n^2/m)/\log{n})$ time, improving the best known bound for dense nonbipartite graphs. Also other theoretical and algorithmic results on skew-symmetric flows and their applications are presented.
Goldberg Andrew V.
Karzanov Alexander V.
No associations
LandOfFree
Maximum Skew-Symmetric Flows and Matchings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Maximum Skew-Symmetric Flows and Matchings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Maximum Skew-Symmetric Flows and Matchings will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-218082