Tutte seminar - Steve ChaplickExport this event to calendar

Friday, April 13, 2012 — 3:30 PM to 4:30 PM EDT

Path Graphs, PR-trees, and Split Decomposition

Speaker: Steve Chaplick
Affiliation: Wilfrid Laurier University
Room: Mathematics & Computer Building (MC) 5158

Abstract:

Path graphs are the intersection graphs of paths in trees. In this talk we introduce a new data structure, the PR-tree, to characterize the sets of path-tree models of path graphs. We then describe an O(nm) time algorithm to construct a PR-tree from a given graph via Split Decomposition (note: this matches the best known recognition algorithm for path graphs). From this algorithm we provide a new characterization of path graphs by split decomposition. Finally, we show that an implicit form of the PR-tree can be represented in O(n) space.

Note: for those familiar with PQ-trees and interval graphs (i.e., the intersection graphs of subpaths of a path), the PR-tree represents path graphs in the same way that the PQ-tree represents interval graphs (i.e., the PQ-tree of an interval graph G represents the set of all permutations of the maximal cliques of G where the maximal cliques incident with each vertex occur consecutively).

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

Waterloo, ON N2L 3G1
Canada

S M T W T F S
26
27
28
29
30
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. 2021 (95)
    1. November (2)
    2. October (6)
    3. September (12)
    4. August (6)
    5. July (10)
    6. June (12)
    7. May (7)
    8. April (9)
    9. March (13)
    10. February (8)
    11. January (10)
  2. 2020 (119)
    1. December (5)
    2. November (12)
    3. October (12)
    4. September (12)
    5. August (11)
    6. July (17)
    7. June (11)
    8. May (6)
    9. March (11)
    10. February (11)
    11. January (11)
  3. 2019 (167)
  4. 2018 (136)
  5. 2017 (103)
  6. 2016 (137)
  7. 2015 (136)
  8. 2014 (88)
  9. 2013 (48)
  10. 2012 (39)
  11. 2011 (36)
  12. 2010 (40)
  13. 2009 (40)
  14. 2008 (39)
  15. 2007 (15)