Average-case analysis of algorithms for matchings and related problems

DOI10.1145/195613.195663MaRDI QIDQ4327634zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Rajeev Motwani

Publication date 10 April 1995

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/195613.195663

zbMATH Keywords

random graphsaugmenting-path algorithmsDinic's algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Matching algorithms are fast in sparse random graphs
• STACS 2004
• Finding maximum matchings in random regular graphs in linear expected time
• Perfect matchings in O(n n) time in regular bipartite graphs
• Perfect matchings in O(n n) time in regular bipartite graphs

Cited in

(18)

• Linear time approximation algorithms for~degree~constrained subgraph problems
• Average-case analysis of some plurality algorithms
• Tight bounds for minimax grid matching with applications to the average case analysis of algorithms
• Maximum likelihood analysis of the Ford-Fulkerson method on special graphs
• On the complexity of the herding attack and some related attacks on hash functions
• Balanced allocation and dictionaries with tightly packed constant size bins
• Approximation algorithms in combinatorial scientific computing
• Expected time complexity of the auction algorithm and the push relabel algorithm for maximum bipartite matching on random graphs
• STACS 2004
• The Metropolis algorithm for graph bisection
• A tight bound for shortest augmenting paths on trees
• Packing vertices and edges in random regular graphs
• scientific article; zbMATH DE number 437526 (Why is no real title available?)
• Matching algorithms are fast in sparse random graphs
• Approximate congruence in nearly linear time
• Finite Termination of “Augmenting Path” Algorithms in the Presence of Irrational Problem Data
• scientific article; zbMATH DE number 18539 (Why is no real title available?)
• Output sensitive fault tolerant maximum matching

This page was built for publication: Average-case analysis of algorithms for matchings and related problems

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