Expected time complexity of the auction algorithm and the push relabel algorithm for maximum bipartite matching on random graphs

DOI10.1002/rsa.20578zbMath1332.05129arXiv1401.0119OpenAlexW2153617527MaRDI QIDQ2795749

Oshri Naparstek, Amir Leshem

Publication date: 22 March 2016

Published in: Random Structures & Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

complexityrandom graphsbipartite matchingauction algorithmpushrelabel algorithm

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• A forward/reverse auction algorithm for asymmetric assignment problems
• An efficient cost scaling algorithm for the assignment problem
• Matching algorithms are fast in sparse random graphs
• TWO THEOREMS IN GRAPH THEORY
• Finding a maximum matching in a sparse random graph in O ( n ) expected time
• A new approach to the maximum-flow problem
• Average-case analysis of algorithms for matchings and related problems
• Power balance and apportionment algorithms for the United States Congress
• On the existence of a factor of degree one of a connected random graph
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: Expected time complexity of the auction algorithm and the push relabel algorithm for maximum bipartite matching on random graphs