Global Price Updates Help

DOI10.1137/S0895480194281185MaRDI QIDQ4377450zbMATH OpenOpenAlexFDO

Authors

Publication date 9 February 1998

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0895480194281185

zbMATH Keywords

assignment problembipartite matchingcost scalingdual updatepush-relabel algorithmzero-one flow

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Deterministic network models in operations research (90B10) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Faster scaling algorithms for general graph matching problems
• Minimum-cost flows in unit-capacity networks
• Power balance and apportionment algorithms for the United States Congress
• The cost scaling algorithm for bipartite networks

Cited in

(6)

• Minimum-cost flows in unit-capacity networks
• An efficient cost scaling algorithm for the assignment problem
• The assignment problem revisited
• Linear-time approximation for maximum weight matching
• A simple reduction from maximum weight matching to maximum cardinality matching
• Efficient algorithms for maximum weight matchings in general graphs with small edge weights

This page was built for publication: Global Price Updates Help

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4377450)