- This event has passed.

# Eunjin Oh (오은진), Feedback Vertex Set on Geometric Intersection Graphs

## Tuesday, October 5, 2021 @ 4:30 PM - 5:30 PM KST

Room B232,
IBS (기초과학연구원)

I am going to present an algorithm for computing a feedback vertex set of a unit disk graph of size k, if it exists, which runs in time $2^{O(\sqrt{k})}(n + m)$, where $n$ and $m$ denote the numbers of vertices and edges, respectively. This improves the $2^{O(\sqrt{k}\log k)}(n + m)$-time algorithm for this problem on unit disk graphs by Fomin et al. [ICALP 2017].