University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Tutte seminar - Alan FriezeExport this event to calendar

Friday, May 22, 2009 — 3:30 PM to 4:30 PM EDT

The Karp-Sipser Matching Algorithm and Refinements

Speaker: Alan Frieze
Affiliation: Carnegie Mellon University
Room: Mathematics & Computer Building (MC) 5158

Abstract:

Karp and Sipser (1981) proposed a simple greedy matching algorithm that they showed to work surprisingly well on sparse random graphs. In addition they showed a remarkable transition in the algorithm's performance at average degree e=2.718.... . In 1998 Aronson,F,Pittel gave a sharper analysis and I will try to give a quick overview of this. More recently, Bohman and F. have applied the algorithm to random graphs with a fixed degree sequence satisfying a log-concavity condition. We describe how this condition enables one to analyse the K-S algorithm in this context. Finally, A,F,P had shown that whp K-S only makes very few "mistakes" and this raises the possibility of fixing these mistakes via an augmenting path algorithm in o(n) time, making O(n) time altogether. We show how this can be done, in joint work with P. Chebolu and P. Melsted.

Location 
MC - Mathematics & Computer Building
5158
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
  1. 2020 (33)
    1. March (11)
    2. February (11)
    3. January (11)
  2. 2019 (167)
    1. December (5)
    2. November (15)
    3. October (18)
    4. September (15)
    5. August (9)
    6. July (17)
    7. June (18)
    8. May (16)
    9. April (9)
    10. March (24)
    11. February (13)
    12. January (8)
  3. 2018 (138)
  4. 2017 (103)
  5. 2016 (137)
  6. 2015 (136)
  7. 2014 (88)
  8. 2013 (48)
  9. 2012 (39)
  10. 2011 (36)
  11. 2010 (40)
  12. 2009 (40)
  13. 2008 (39)
  14. 2007 (15)