3 citations · 5 across the 5 of their papers we have counts for
9 papers
Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover
Florent Foucaud, Esther Galby, Liana Khazaliya +4
Treewidth (tw) is an important parameter that, when bounded, yields tractability for many problems. For example, graph problems expressible in Monadic Second Order (MSO) logic and…
Hardness of Metric Dimension in Graphs of Constant Treewidth
Shaohua Li, Marcin Pilipczuk
The Metric Dimension problem asks for a minimum-sized resolving set in a given (unweighted, undirected) graph . Here, a set is resolving if no two distinct ve…
The Complexity of Connectivity Problems in Forbidden-Transition Graphs and Edge-Colored Graphs
Thomas Bellitto, Shaohua Li, Karolina Okrasa +2
The notion of forbidden-transition graphs allows for a robust generalization of walks in graphs. In a forbidden-transition graph, every pair of edges incident to a common vertex is…
Many visits TSP revisited
Łukasz Kowalik, Shaohua Li, Wojciech Nadara +2
We study the Many Visits TSP problem, where given a number for each of cities and pairwise (possibly asymmetric) integer distances, one has to find an optimal tour that…
An Improved FPT Algorithm for the Flip Distance Problem
Qilong Feng, Shaohua Li, Xiangzhong Meng +1
Given a set of points in the Euclidean plane and two triangulations of , the flip distance between these two triangulations is the minimum number of flips required…
Cluster Editing parameterized above modification-disjoint -packings
Shaohua Li, Marcin Pilipczuk, Manuel Sorge
Given a graph and an integer , the Cluster Editing problem asks whether we can transform into a union of vertex-disjoint cliques by at most modifications (edge…
Multi-budgeted directed cuts
Stefan Kratsch, Shaohua Li, Dániel Marx +2
We study multi-budgeted variants of the classic minimum cut problem and graph separation problems that turned out to be important in parameterized complexity: Skew Multicut and Dir…
An improved FPT algorithm for Independent Feedback Vertex Set
Shaohua Li, Marcin Pilipczuk
We study the Independent Feedback Vertex Set problem - a variant of the classic Feedback Vertex Set problem where, given a graph and an integer , the problem is to decide wh…
Cascade hash tables: a series of multilevel double hashing schemes with O(1) worst case lookup time
Shaohua Li
In this paper, the author proposes a series of multilevel double hashing schemes called cascade hash tables. They use several levels of hash tables. In each table, we use the commo…