University of Waterloo COVID-19 update

The University of Waterloo is constantly updating its most frequently asked questions.

Questions about buildings and services? Please visit the list of modified services.

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

PhD Seminar • Algorithms and Complexity — End-Vertices of AT-free BigraphsExport this event to calendar

Wednesday, April 15, 2020 — 1:30 PM EDT

Please note: This PhD seminar will be given online.

Jan Gorzny, PhD candidate
David R. Cheriton School of Computer Science

The end-vertex problem for a search algorithm asks whether a vertex of the input graph is the last visited vertex of an execution of that search algorithm. This problem has been studied for various classes of graphs including chordal graphs, interval graphs, and AT-free graphs. After reviewing some recent results, we will consider the end-vertex problem restricted to AT-free bigraphs for various search algorithms: Breadth First Search (BFS), Lexicographic Breadth First Search (LBFS), Depth-First Search (DFS), and Maximal Neighborhood Search (MNS). Deciding whether a vertex of a graph is the end-vertex of any of these search algorithms is NP-complete in general. 

We will show that we can decide whether a vertex is an end-vertex of BFS or MNS in polynomial time on AT-free bigraphs. Additionally, we will show that we can decide whether a vertex is an end-vertex of DFS or LBFS in linear time on AT-free graphs; this improves the LBFS end-vertex complexity on this class of graphs.

Location 
Online PhD seminar
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
29
30
31
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
1
2
  1. 2020 (76)
    1. May (3)
    2. April (9)
    3. March (17)
    4. February (25)
    5. January (22)
  2. 2019 (255)
    1. December (21)
    2. November (25)
    3. October (16)
    4. September (20)
    5. August (18)
    6. July (12)
    7. June (23)
    8. May (23)
    9. April (32)
    10. March (25)
    11. February (16)
    12. January (24)
  3. 2018 (220)
  4. 2017 (36)
  5. 2016 (21)
  6. 2015 (36)
  7. 2014 (33)
  8. 2013 (23)
  9. 2012 (4)
  10. 2011 (1)
  11. 2010 (1)
  12. 2009 (1)
  13. 2008 (1)