On Covering Segments with Unit Intervals

DOI10.1137/20M1336412MaRDI QIDQ5864214

Dan Bergren, Robert Ganian, Eduard Eiben, Iyad A. Kanj

Publication date: 3 June 2022

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/20m1336412

zbMATH Keywords

NP-completeness; parameterized complexity; unit intervals; segment covering

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q27: Parameterized complexity, tractability and kernelization

Cites Work

• Unnamed Item
• Unnamed Item
• Parameterized complexity dichotomy for \textsc{Steiner Multicut}
• Fundamentals of parameterized complexity
• Incremental list coloring of graphs, parameterized by conservation
• A parameterized algorithm for the hyperplane-cover problem
• Machine-based methods in parameterized complexity theory
• Unit disk graphs
• Stabbing circles for sets of segments in the plane
• Selecting and covering colored points
• Drawing planar graphs using the canonical ordering
• Covering things with things
• Complexity results on restricted instances of a paint shop problem for words
• Graph Theory
• The Approximability of the Binary Paintshop Problem
• Choice Is Hard
• PTAS for Weighted Set Cover on Unit Squares
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The Complexity of Combinatorial Optimization Problems on d‐Dimensional Boxes
• Parameterized Algorithms
• On Structural Parameterizations of Hitting Set: Hitting Paths in Graphs Using 2-SAT
• Covering segments with unit squares