Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


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



ID: 231169.0, MPI für Informatik / Algorithms and Complexity Group
Matching Algorithms Are Fast in Sparse Random Graphs
Authors:Bast, Holger; Mehlhorn, Kurt; Schäfer, Guido; Tamaki, Hisao
Editors:Diekert, Volker; Habib, Michel
Language:English
Publisher:Springer
Place of Publication:Berlin, Germany
Date of Publication (YYYY-MM-DD):2004
Title of Proceedings:21st Annual Symposium on Theoretical Aspects of Computer Science (STACS-04)
Start Page:81
End Page:92
Title of Series:Lecture Notes in Computer Science
Place of Conference/Meeting:Montpellier, France
(Start) Date of Conference/Meeting
 (YYYY-MM-DD):
2004-03-25
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 nonmaximum
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(mpn), run in time O(mlog 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) [Average Case Analysis of
Algorithms for Matchings and Related Problems, Journal of the ACM, 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):2005-05-23
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Kurt Mehlhorn
Affiliations:MPI für Informatik/Algorithms and Complexity Group
Identifiers:LOCALID:C1256428004B93B8-1F79D167AE1C3869C1256F9500480213-...
ISBN:3-540-21236-1
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.