this week we will have seminar given by a vising grad student from Slovenia.
The seminar is in the usual time slot. I'm writing this a bit earlier in case you may want to discuss something (I believe she only stays this week).
Title: On the End-Vertex Problem of Graph Searches
Speaker: Nevena Pivač (University of Primorska)
End vertices of graph searches can exhibit strong structural properties
and are crucial for many graph algorithms. In the lecture we will
present a selection of known and new results related to end vertices of
various graph searches.
The problem of deciding whether a given vertex of a graph is an end
vertex of a particular search was first introduced by Corneil, Köohler,
and Lanlignel in 2010. There they showed that this problem is in fact
NP-complete for LBFS on weakly chordal graphs. A similar result for BFS
was obtained by Charbit, Habib and Mamcarz in 2014.
Regarding new results, we prove that the end-vertex problem is
NP-complete for MNS on weakly chordal graphs and for MCS on general
graphs. Moreover, building on previous results, we show that this
problem is linear-time solvable for various searches on split and unit
interval graphs.
Joint work with Jesse Beisegel, Carolin Denkert, Ekkehard Köhler, Matjaž
Krnc, Robert Scheffler, Martin Strehler. Preprint available at
https://arxiv.org/abs/1810.12253.