Browsing University of Bergen Library by Author "Jacob, Hugo"
Now showing items 1-2 of 2
-
XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure
Bodlaender, Hans L.; Groenland, Carla; Jacob, Hugo; Jaffke, Lars; Lima, Paloma Thome de (Journal article; Peer reviewed, 2022)In this paper, we showcase the class XNLP as a natural place for many hard problems parameterized by linear width measures. This strengthens existing W[1]-hardness proofs for these problems, since XNLP-hardness implies ... -
XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure
Bodlaender, Hans L.; Groenland, Carla; Jacob, Hugo; Jaffke, Lars; Lima, Paloma T. (Journal article; Peer reviewed, 2024)In this paper, we showcase the class XNLP as a natural place for many hard problems parameterized by linear width measures. This strengthens existing W[1]-hardness proofs for these problems, since XNLP-hardness implies ...