Browsing Department of Informatics by Author "Jaffke, Lars"

Now showing items 21-27 of 27

    • Treewidth is NP-Complete on Cubic Graphs 

      Bodlaender, Hans L.; Bonnet, Édouard; Jaffke, Lars; Knop, Dusan; Lima, Paloma Thome de; Milanič, Martin; Ordyniak, Sebastian; Pandey, Sukanya; Suchy, Ondrey (Journal article; Peer reviewed, 2023)
      In this paper, we show that Treewidth is NP-complete for cubic graphs, thereby improving the result by Bodlaender and Thilikos from 1997 that Treewidth is NP-complete on graphs with maximum degree at most 9. We add a new ...

    • Typical Sequences Revisited - Computing Width Parameters of Graphs 

      Bodlaender, Hans L.; Jaffke, Lars; Telle, Jan Arne (Journal article; Peer reviewed, 2021)
      In this work, we give a structural lemma on merges of typical sequences, a notion that was introduced in 1991 [Lagergren and Arnborg, Bodlaender and Kloks, both ICALP 1991] to obtain constructive linear time parameterized ...

    • Typical Sequences Revisited – Computing Width Parameters of Graphs 

      Bodlaender, Hans L.; Jaffke, Lars; Telle, Jan Arne (Journal article; Peer reviewed, 2020)
      In this work, we give a structural lemma on merges of typical sequences, a notion that was introduced in 1991 [Lagergren and Arnborg, Bodlaender and Kloks, both ICALP 1991] to obtain constructive linear time parameterized ...

    • A Unifying Framework for Characterizing and Computing Width Measures 

      Eiben, Eduard; Ganian, Robert; Hamm, Thekla; Jaffke, Lars; Kwon, O-joung (Journal article; Peer reviewed, 2022)
      Algorithms for computing or approximating optimal decompositions for decompositional parameters such as treewidth or clique-width have so far traditionally been tailored to specific width parameters. Moreover, for mim-width, ...

    • Well-partitioned chordal graphs 

      Ahn, Jungho; Jaffke, Lars; Kwon, O-joung; Lima, Paloma T. (Journal article; Peer reviewed, 2022)
      We introduce a new subclass of chordal graphs that generalizes the class of split graphs, which we call well-partitioned chordal graphs. A connected graph G is a well-partitioned chordal graph if there exist a partition P ...

    • What Is Known About Vertex Cover Kernelization? 

      Fellows, Michael R.; Jaffke, Lars; Király, Aliz Izabella; Rosamond, Frances; Weller, Mathias (Peer reviewed; Journal article, 2018)
      We are pleased to dedicate this survey on kernelization of the Vertex Cover problem, to Professor Juraj Hromkovič on the occasion of his 60th birthday. The Vertex Cover problem is often referred to as the Drosophila of ...

    • 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 ...