On Covering Segments with Unit Intervals
From MaRDI portal
Publication:5864214
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
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