DLS: Robert Tarjan - From Dominators to Disjoint Sets and BackExport this event to calendar

Thursday, October 22, 2015 3:30 PM EDT

Robert TarjanRobert Tarjan
James S. McDonnell Distinguished University Professor
Princeton University

Abstract: Efficient algorithms for many problems rely on the proper choice of data structures. An interesting example of this is the problem of finding dominators in a directed graph. The dominators problem arises in global computer code optimization, hardware verification, and food web analysis, among other places. I'll describe work done on this problem and on related data structures over the last 40 years. Even though the problem has been heavily studied for a long time, new discoveries continue to be made.

Biography: Robert Tarjan is the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University, and a senior fellow at Hewlett-Packard. His research is in the field of algorithms and data structures. He has developed linear time algorithms for testing a host of graph properties including planarity and multiconnectivity. His closely related work on efficient data structures has led to splay trees, persistent data structures and Fibonacci heaps, among others.

Professor Tarjan has been recognized with many major awards, most notably the Turing Award, which is the most prestigious in computer science. He earned a BS degree in mathematics from the California Institute of Technology, and MS and PhD degrees in computer science from Stanford University. He has held academic positions at Cornell University, the University of California at Berkeley, Stanford University, New York University, Massachusetts Institute of Technology, and Princeton University.
Location 
HH - J.G. Hagey Hall of the Humanities

200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
25
26
27
28
29
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
5
6
  1. 2024 (96)
    1. April (19)
    2. March (27)
    3. February (25)
    4. January (25)
  2. 2023 (296)
    1. December (20)
    2. November (28)
    3. October (15)
    4. September (25)
    5. August (30)
    6. July (30)
    7. June (22)
    8. May (23)
    9. April (32)
    10. March (31)
    11. February (18)
    12. January (22)
  3. 2022 (245)
  4. 2021 (210)
  5. 2020 (217)
  6. 2019 (255)
  7. 2018 (217)
  8. 2017 (36)
  9. 2016 (21)
  10. 2015 (36)
  11. 2014 (33)
  12. 2013 (23)
  13. 2012 (4)
  14. 2011 (1)
  15. 2010 (1)
  16. 2009 (1)
  17. 2008 (1)