Huairui Chu

activity

20202026

most citedA Tight Lower Bound for Compact Set Packing

1 citations · 1 across the 5 of their papers we have counts for

collaborators

Showing cs.DSShow all

3 papers · 1 filter

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.DS2024

FPT Approximation using Treewidth: Capacitated Vertex Cover, Target Set Selection and Vector Dominating Set

Huairui Chu, Bingkai Lin

Treewidth is a useful tool in designing graph algorithms. Although many NP-hard graph problems can be solved in linear time when the input graphs have small treewidth, there are pr…

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…