Efficient Minimum Cost Matching and Transportation Using the Quadrangle Inequality

DOI10.1006/jagm.1995.1030zbMath0849.68043OpenAlexW1990238495MaRDI QIDQ4840222

Baruch Schieber, Samir Khuller, Alok Aggarwal, Dina Kravets, Amotz Bar-Noy

Publication date: 4 November 1996

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1903/610

zbMATH Keywords

bitonic Monge array

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Related Items (9)

Simple linear flow decomposition algorithms on trees, circles, and augmented trees ⋮ The Complexity of Finding Small Separators in Temporal Graphs ⋮ New variants of perfect non-crossing matchings ⋮ Minimum-weight perfect matching for nonintrinsic distances on the line ⋮ Planar graphs, negative weight edges, shortest paths, and near linear time ⋮ Resilient capacity-aware routing ⋮ Faster strongly polynomial algorithms for the unbalanced transportation problem and assignment problem with monge costs ⋮ Fast algorithms for convex cost flow problems on circles, lines, and trees ⋮ An algorithm for computing the restriction s|caffold assignment problem in computational biology

This page was built for publication: Efficient Minimum Cost Matching and Transportation Using the Quadrangle Inequality