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.
200 University Avenue West
Waterloo, ON N2L 3G1