Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

 
 
DownloadE-Mail
  Matching Algorithms Are Fast in Sparse Random Graphs

Bast, H., Mehlhorn, K., Schäfer, G., & Tamaki, H. (2004). Matching Algorithms Are Fast in Sparse Random Graphs. In 21st Annual Symposium on Theoretical Aspects of Computer Science (STACS-04) (pp. 81-92). Berlin, Germany: Springer.

Item is

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Bast, Holger1, Autor           
Mehlhorn, Kurt1, Autor           
Schäfer, Guido1, Autor           
Tamaki, Hisao1, Autor           
Diekert, Volker, Herausgeber
Habib, Michel, Herausgeber
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Inhalt

einblenden:
ausblenden:
Schlagwörter: -
 Zusammenfassung: 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.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2005-05-232004
 Publikationsstatus: Erschienen
 Seiten: -
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: eDoc: 231169
Anderer: Local-ID: C1256428004B93B8-1F79D167AE1C3869C1256F9500480213-bast04stacs
 Art des Abschluß: -

Veranstaltung

einblenden:
ausblenden:
Titel: Untitled Event
Veranstaltungsort: Montpellier, France
Start-/Enddatum: 2004-03-25

Entscheidung

einblenden:

Projektinformation

einblenden:

Quelle 1

einblenden:
ausblenden:
Titel: 21st Annual Symposium on Theoretical Aspects of Computer Science (STACS-04)
Genre der Quelle: Konferenzband
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: Berlin, Germany : Springer
Seiten: - Band / Heft: - Artikelnummer: - Start- / Endseite: 81 - 92 Identifikator: ISBN: 3-540-21236-1

Quelle 2

einblenden:
ausblenden:
Titel: Lecture Notes in Computer Science
Genre der Quelle: Reihe
 Urheber:
Affiliations:
Ort, Verlag, Ausgabe: -
Seiten: - Band / Heft: 2996 Artikelnummer: - Start- / Endseite: - Identifikator: -