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