Maximum skew-symmetric flows and matchings

DOI10.1007/s10107-004-0505-zzbMath1070.90090arXivmath/0304290MaRDI QIDQ1885276

Andrew V. Goldberg, Alexander V. Karzanov

Publication date: 28 October 2004

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0304290

zbMATH Keywords

matching; network flow; b-matching; skew-symmetric graph

Mathematics Subject Classification ID

90C10: Integer programming

90B10: Deterministic network models in operations research

90C27: Combinatorial optimization

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs, Unnamed Item, Faster algorithms for half-integral T -Path packing, Approximation algorithms for the directed path partition problems, An algorithm for \((n-3)\)-connectivity augmentation problem: jump system approach, On flows in simple bidirected and skew-symmetric networks, A simple reduction from maximum weight matching to maximum cardinality matching, Greedy matching: guarantees and limitations, Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization, A cubic kernel for feedback vertex set and loop cutset, Minimum mean cycle problem in bidirected and skew-symmetric graphs, A fast scaling algorithm for the weighted triangle-free 2-matching problem, Min-cost multiflows in node-capacitated undirected networks, A local search 4/3-approximation algorithm for the minimum 3-path partition problem, Faster algorithm for finding maximum 1-restricted simple 2-matchings, Making bidirected graphs strongly connected, Faster graph bipartization, Free multiflows in bidirected and skew-symmetric graphs, An improved approximation algorithm for the minimum 3-path partition problem, Linear Time Approximation Algorithms for Degree Constrained Subgraph Problems, Linear-Time Approximation for Maximum Weight Matching