Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, April 22, 2021, 12:15 pm
Duration: 30 minutes
Location: Zoom: conference room
Speaker: Hung Hoang
Suppose we run a train on a directed (multi-)graph, where every vertex has out-degree 2 and is equipped with a switch. At the beginning, the switch at each vertex points to one of the two outgoing edges. When the train reaches a vertex, it will traverse along the edge pointed by the switch, and then the switch at that vertex shifts to the other outgoing edge. Given such a graph with an origin vertex o and a destination vertex d, the problem is to decide if the train starting from o can reach d.
The problem above is called ARRIVAL. It is in NP and co-NP, but not known to be in P. The currently best algorithms have runtime 2^ϴ(n) where n is the number of vertices. This is not much better than just performing the pseudorandom walk. In this talk, I will present a subexponential algorithm with runtime 2^O(√n log n).
Joint work with Bernd Gärtner and Sebastian Haslebacher
Automatic MiSe System Software Version 1.4803M | admin login