Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, February 28, 2019, 12:15 pm
Duration: 30 minutes
Location: CAB G51
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 known that the problem is in NP and co-NP. The open question is whether it is in P. In this talk, I will present a combinatorial algorithm that runs in time O(2^(n/2)) and a polynomial time algorithm for a subclass of the problem. The latter is by modelling the problem as an integer programme and examining the primal and dual of the linear relaxation.
Automatic MiSe System Software Version 1.4803M | admin login