3 citations · 5 across the 5 of their papers we have counts for
7 papers · 1 filter
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…
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…