Author name cluster

Wenfeng Lai

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

I&C Journal 2025 Journal Article

The longest subsequence-duplicated subsequence and related problems

Manuel Lafond
Wenfeng Lai
Adiesha Liyanage
Binhai Zhu

Motivated by computing duplication patterns in sequences, a new fundamental problem called the longest subsequence-duplicated subsequence (LSDS) is proposed. Given a sequence S of length n, a subsequence-duplicated subsequence is a subsequence of S in the form of x 1 d 1 x 2 d 2 ⋯ x k d k with x i being a subsequence of S, x j ≠ x j + 1 and d i ≥ 2 for all i in [ k ] and j in [ k − 1 ]. We first present an O ( n 6 ) time algorithm to compute the longest cubic subsequences of all the O ( n 2 ) substrings of S, improving the trivial O ( n 7 ) bound. Then, an O ( n 6 ) time algorithm for computing the longest subsequence-duplicated subsequence (LSDS) of S is obtained. Finally we focus on two variants of this problem. We first consider the constrained version when Σ is unbounded, each letter appears in S at most d times and all the letters in Σ must appear in the solution. We show that the problem is NP-hard for d = 4, via a reduction from a special version of SAT (which is obtained from 3-COLORING). We then show that when each letter appears in S at most d = 3 times, then the problem is solvable in O ( n 4 ) time.

Details DOI

TCS Journal 2021 Journal Article

Dispersing and grouping points on planar segments

Xiaozhou He
Wenfeng Lai
Binhai Zhu
Peng Zou

Motivated by (continuous) facility location, we study the problem of dispersing and grouping points on a set of segments (of streets) in the plane. In the former problem, given a set of n disjoint line segments in the plane, we investigate the problem of computing a point on each of the n segments such that the minimum Euclidean distance between any two of these points is maximized. We prove that this 2D dispersion problem is NP-hard, in fact, it is NP-hard even if all the segments are parallel and are of unit length. This is in contrast to the polynomial solvability of the corresponding 1D problem by Li and Wang (2016), where the intervals are in 1D and are all disjoint. With this result, we also show that the Independent Set problem on Colored Linear Unit Disk Graph (meaning the convex hulls of points with the same color form disjoint line segments) remains NP-hard, and the parameterized version of it is in W[2]. In the latter problem, given a set of n disjoint line segments in the plane we study the problem of computing a point on each of the n segments such that the maximum Euclidean distance between any two of these points is minimized. We present a factor-1. 1547 approximation algorithm which runs in O ( n log ⁡ n ) time. Our results can be generalized to the Manhattan distance.

Details DOI