Some efficient algorithms for the k-vertex cover problem
- Speaker
- Yijia Chen
- Affiliation
- Shanghai Jiao Tong University
- Date
- Time
- – Asia/Shanghai
- 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》编委。
Schedule
- 11:00-12:00 (Time in Beijing)
- 15:00-16:00 (Time in Auckland)
- May 20, 2021 (Thursday)