Speaker:
Yijia Chen(Shanghai Jiao Tong University)
Time:
- 11:00-12:00 (Time in Beijing)
- 15:00-16:00 (Time in Auckland)
- May 20, 2021 (Thursday)
Venue:
B1-501, Main Building
Abstract:
Let k be a fixed constant. The k-vertex cover problem asks, for an input graph G, whether G contains k vertices which intersect every edge in G. The problem has been studied extensively both in theory and practice. In fact, when k is a part of the input, the problem becomes NP-hard. So it might seem that the trivial n^{O(k)}-time algorithm is the best we can achieve. However, in this talk, I will discuss various techniques to design much better algorithms for the k-vertex cover problem, showing that it is solvable in linear time. Moreover, on a massive parallel computer, the problem can be even decided in merely 34 steps.
Speaker Bio:
陈翌佳现为上海交通大学计算机系教授。他在上海交通大学获得软件计算与理论博士学位，在德国弗莱堡大学获得数学博士学位。他的研究领域是逻辑、计算复杂性以及算法图论。他目前担任国际期刊《Logic Methods in Computer Science》和《Theory ofComputing Systems》编委。