Nearly time-optimal kernelization algorithms for the line-cover problem with big data

DOI10.1007/s00453-024-01231-6MaRDI QIDQ6586656

Ge Xia, Qin Huang, Jian'er Chen, Iyad A. Kanj

Publication date: 13 August 2024

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

parameterized computationline coverkernelization algorithmNP-complete geometric problem

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A parameterized algorithm for the hyperplane-cover problem
• Cutting hyperplanes for divide-and-conquer
• On randomized one-round communication complexity
• Algorithmic graph embeddings
• On the complexity of locating linear facilities in the plane
• Linear-time parameterized algorithms with limited local resources
• Tabulation-Based 5-Independent Hashing with Applications to Linear Probing and Second Moment Estimation
• Streaming Kernelization
• Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms
• Covering a Set of Points with a Minimum Number of Lines
• Towards an Optimal Method for Dynamic Planar Point Location
• Point Line Cover
• Dynamic Parameterized Problems and Algorithms
• Faster Update Time for Turnstile Streaming Algorithms
• Statistical Models
• Parameterized Algorithms
• Towards a theory of parameterized streaming algorithms
• Dynamic planar point location in optimal time
• Filling Crosswords is Very Hard
• Space limited linear-time graph algorithms on big data

This page was built for publication: Nearly time-optimal kernelization algorithms for the line-cover problem with big data