Journal Article @Article Artikel in Fachzeitschrift
 Show entries of: this year (2019) | last year (2018) | two years ago (2017) | Notes URL
 Action: login to update Options: Goto entry point

 Author, Editor(s)
 Author(s): Bast, Holger Mehlhorn, Kurt Schäfer, Guido Tamaki, Hisao dblp dblp dblp dblp Not MPG Author(s): Tamaki, Hisao
 BibTeX cite key*: BMST05

 Title
 Title*: Matching Algorithms are Fast in Sparse Random Graphs

 Journal

 Publisher
 Publisher's Name: Springer Publisher's URL: http://www.springer.com/ Publisher's Address: New York, USA ISSN: 1432-4350

 Vol, No, pp, Date
 Volume*: 39 Number: 1 Publishing Date: February 2006 Pages*: 3-14 Number of VG Pages: Page Start: 3 Page End: 14 Sequence Number: DOI: 10.1007/s00224-005-1254-y

 Note: (LaTeX) Abstract: 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. URL for the Abstract: http://www.springerlink.com/content/7822w6p2r53r1275/?p=a6202488e5d14b229018fde21fede630&pi=1 Categories, Keywords: HyperLinks / References / URLs: Copyright Message: Personal Comments: Download Access Level: Intranet

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@ARTICLE{BMST05,
AUTHOR = {Bast, Holger and Mehlhorn, Kurt and Sch{\"a}fer, Guido and Tamaki, Hisao},
TITLE = {Matching Algorithms are Fast in Sparse Random Graphs},
JOURNAL = {Theory of Computing Systems},
PUBLISHER = {Springer},
YEAR = {2006},
NUMBER = {1},
VOLUME = {39},
PAGES = {3--14},