Institute: MPI für Informatik     Collection: Algorithms and Complexity Group     Display Documents

ID: 314609.0, MPI für Informatik / Algorithms and Complexity Group
Matching Algorithms are Fast in Sparse Random Graphs
Authors:
Language:English
Date of Publication (YYYY-MM-DD):2006
Title of Journal:Theory of Computing Systems
Volume:39
Start Page:3
End Page:14
Review Status:Peer-review
Audience:Experts Only
Intended Educational Use:No
Abstract / Description:We present an improved average case analysis of the maximum cardinality
matching problem. We show that in a bipartite or general random graph on $n$
vertices, with high probability every non-maximum matching has an augmenting
path of length $O(\log n)$. This implies that augmenting path algorithms like
the Hopcroft--Karp algorithm for bipartite graphs and the Micali--Vazirani
algorithm for general graphs, which have a worst case running time of
$O(m\sqrt{n})$, run in time $O(m \log n)$ with high probability, where $m$ is
the number of edges in the graph. Motwani proved these results for random
graphs when the average degree is at least $\ln (n)$ [\emph{Average Case
Analysis of Algorithms for Matchings and Related Problems}, Journal of the ACM,
\textbf{41}(6), 1994]. Our results hold, if only the average degree is a large
enough constant. At the same time we simplify the analysis of Motwani.
Last Change of the Resource (YYYY-MM-DD):2006-10-04
External Publication Status:published
Document Type:Article
Communicated by:Kurt Mehlhorn
Affiliations:
Identifiers:LOCALID:C1256428004B93B8-257B5C3871441CAAC1256FC0004404AB-...
ISSN:1432-4350
 Full Text: Sorry, no privileges
 The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.