Qin Huang 0008

dblp:46/4826-8 · DBLP profile ↗
← Back
4ranked-venue papers
0as first author
4since 2021 · last 2024
—ORCID · conflict

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 4 · 4 since 2021
YearPublicationVenuePosition
2024 Nearly Time-Optimal Kernelization Algorithms for the Line-Cover Problem with Big Data
Jianer Chen, Qin Huang 0008, Iyad Kanj, Ge Xia
Algorithmica2
2022 Near-Optimal Algorithms for Point-Line Covering Problems
Jianer Chen, Qin Huang 0008, Iyad Kanj, Ge Xia
STACS2
2022 Linear-time parameterized algorithms with limited local resources
Jianer Chen, Qin Huang 0008
Inf. Comput.3
2021 Streaming Algorithms for Graph k-Matching with Optimal or Near-Optimal Update Time
abstract
We propose a new (theoretical) computational model for the study of massive data processing with limited computational resources. Our model measures the complexity of reading the very large data sets in terms of the data size N and analyzes the computational cost in terms of a parameter k that characterizes the computational power provided by limited local computing resources. We develop new algorithmic techniques that implement algorithms for solving well-known computational problems on the proposed model. In particular, we present an algorithm that finds a k-matching in a general unweighted graph in time O(N + k^{2.5}) and an algorithm that constructs a maximum weighted k-matching in a general weighted graph in time O(N + k^3 log k). Both algorithms have their space complexity bounded by O(k^2).
Jianer Chen, Qin Huang 0008, Iyad Kanj, Qian Li 0012, Ge Xia
ISAAC2