|
| | | | |
| | | |
| Stat |
Members: 3669
Articles: 2'599'751
Articles rated: 2609
18 March 2025 |
|
| | | | |
|
Article overview
| |
|
|
Parameterized covering in semi-ladder-free hypergraphs | | Sylvain Guillemot
; | | Date: |
1 Nov 2023 | | Abstract: | In this article, we study the parameterized complexity of the Set Cover
problem restricted to d-semi-ladder-free hypergraphs, a class defined by
Fabianski et al. [Proceedings of STACS 2019]. We observe that two algorithms
introduced by Langerman and Morin [Discrete & Computational Geometry 2005] in
the context of geometric covering problems can be adapted to this setting,
yielding simple FPT and kernelization algorithms for Set Cover in
d-semi-ladder-free hypergraphs. We complement our algorithmic results with a
compression lower bound for the problem, that proves the tightness of our
kernelization under standard complexity-theoretic assumptions. | | Source: | arXiv, 2311.00466 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|
REGISTER