Huairui Chu

collaborators

3 papers

cs.CG2026

Parameterized Approximation of Rectangle Stabbing

Huairui Chu, Ajaykrishnan E S, Daniel Lokshtanov +4

In the Rectangle Stabbing problem, input is a set $R$ of axis-parallel rectangles and a set $L$ of axis parallel lines in the plane. The task is to find a minimum siz…

cs.DS2026

Faster Parameterized Vertex Multicut

Huairui Chu, Yuxi Liu, Daniel Lokshtanov +3

In the {\sc Vertex Multicut} problem the input consists of a graph $G$ , integer $k$ , and a set $T = {(s_{1}, t_{1}), \dots, (s_{p}, t_{p})}$ of pairs of vertices of $G$ . The ta…

cs.DS2020

An Improved Upper Bound for SAT

Huairui Chu, Mingyu Xiao, Zhe Zhang

We show that the CNF satisfiability problem can be solved $O^{*} (1.222 6^{m})$ time, where $m$ is the number of clauses in the formula, improving the known upper bounds $O^{*} (1.23 4^{m})$ g…