PhD Seminar • Algorithms and Complexity — End-Vertices of AT-free Bigraphs

Wednesday, April 15, 2020 1:30 pm - 1:30 pm EDT (GMT -04:00)

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.

To join this PhD seminar on Zoom, please go to https://zoom.us/j/9700990248.
Meeting ID: 970 099 0248