Average-case analysis of algorithms for matchings and related problems

1994/11/01 by Rajeev Motwani · 1 citation
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Optimization and Search Problems #Citation #Computer science #Algorithm #Information retrieval #Operations research #World Wide Web #Mathematics

paper · pdf · doi:10.1145/195613.195663

openalex publication_date 1994/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/04/04

Abstract

We analyze the behavior of augmenting paths in random graphs. Our results show that in almost every graph, any nonmaximum O-1 flow admits a short augmenting path. This enables us to prove that augmenting-path algorithms, that are fast in the worst case, also perform exceedingly well on the average. In particular, we show that the 0(~1 El) algorithms for bipartite and general matchings run in almost linear time with high probability.

Citations

• The complexity of computing the permanent
• Hamiltonian circuits in random graphs
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• On Representatives of Subsets
• Limit distribution for the existence of hamiltonian cycles in a random graph

Cited by

• Hopcroft–Karp algorithm [wikipedia]