Lars Jaffke

81 papers A* 4A 8B 16C 2Journal 50Unranked 1
YearRankTypeTitle / Venue / Authors
2026 J jnl
Dynamic programming on bipartite tree decompositions.
J. Comput. Syst. Sci.
Lars Jaffke, Laure Morelle, Ignasi Sau, Dimitrios M. Thilikos
2026 J jnl
Hamiltonicity parameterized by mim-width is (indeed) para-NP-hard.
Theor. Comput. Sci.
Benjamin Bergougnoux, Lars Jaffke
2025 B conf
A Parameterized Complexity Analysis of Bounded Height Depth-First Search Trees.
WG
Lars Jaffke, Paloma Thomé de Lima, Wojciech Nadara, Emmanuel Sam
2025 J jnl
A Parameterized Complexity Analysis of Bounded Height Depth-first Search Trees.
CoRR
Lars Jaffke, Paloma T. Lima, Wojciech Nadara, Emmanuel Sam
2025 B conf
Hamiltonicity Parameterized by Mim-Width Is (Indeed) Para-NP-Hard.
IPEC
Benjamin Bergougnoux, Lars Jaffke
2025 J jnl
Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard.
CoRR
Benjamin Bergougnoux, Lars Jaffke
2025 J jnl
Hedonic seat arrangement problems.
Auton. Agents Multi Agent Syst.
Hans L. Bodlaender, Tesshu Hanaka, Lars Jaffke, Hirotaka Ono, Yota Otachi, Tom C. van der Zanden
2025 A conf
On Algorithmic Applications of ℱ-Branchwidth.
ESA
Benjamin Bergougnoux, Thekla Hamm, Lars Jaffke, Paloma T. Lima
2025 J jnl
Treewidth is NP-Complete on Cubic Graphs.
Electron. J. Comb.
Hans L. Bodlaender, Édouard Bonnet, Lars Jaffke, Dusan Knop, Paloma T. Lima, Martin Milanic, Sebastian Ordyniak, Sukanya Pandey, Ondrej Suchý
2025 J jnl
XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure.
Algorithmica
Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Lars Jaffke, Paloma T. Lima
2024 J jnl
Classes of intersection digraphs with good algorithmic properties.
J. Graph Theory
Lars Jaffke, O-joung Kwon, Jan Arne Telle
2024 J jnl
Diverse Pairs of Matchings.
Algorithmica
Fedor V. Fomin, Petr A. Golovach, Lars Jaffke, Geevarghese Philip, Danil Sagunov
2024 J jnl
Taming Graphs with No Large Creatures and Skinny Ladders.
SIAM J. Discret. Math.
Jakub Gajarský, Lars Jaffke, Paloma T. Lima, Jana Masaríková, Marcin Pilipczuk, Pawel Rzazewski, Uéverton S. Souza
2024 J jnl
b-Coloring Parameterized by Clique-Width.
Theory Comput. Syst.
Lars Jaffke, Paloma T. Lima, Daniel Lokshtanov
2023 A* conf
A logic-based algorithmic meta-theorem for mim-width.
SODA
Benjamin Bergougnoux, Jan Dreier, Lars Jaffke
2023 A* conf
A tight quasi-polynomial bound for Global Label Min-Cut.
SODA
Lars Jaffke, Paloma T. Lima, Tomás Masarík, Marcin Pilipczuk, Uéverton S. Souza
2023 B conf
Dynamic Programming on Bipartite Tree Decompositions.
IPEC
Lars Jaffke, Laure Morelle, Ignasi Sau, Dimitrios M. Thilikos
2023 J jnl
Dynamic programming on bipartite tree decompositions.
CoRR
Lars Jaffke, Laure Morelle, Ignasi Sau, Dimitrios M. Thilikos
2023 J jnl
Fine-grained parameterized complexity analysis of graph coloring problems.
Discret. Appl. Math.
Lars Jaffke, Bart M. P. Jansen
2023 A* conf
Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation.
SODA
Meike Hatzel, Lars Jaffke, Paloma T. Lima, Tomás Masarík, Marcin Pilipczuk, Roohani Sharma, Manuel Sorge
2023 J jnl
On the maximum number of edges in planar graphs of bounded degree and matching number.
Discret. Math.
Lars Jaffke, Paloma T. Lima
2023 B conf
Structural Parameterizations of b-Coloring.
ISAAC
Lars Jaffke, Paloma T. Lima, Roohani Sharma
2023 B conf
Treewidth Is NP-Complete on Cubic Graphs.
IPEC
Hans L. Bodlaender, Édouard Bonnet, Lars Jaffke, Dusan Knop, Paloma T. Lima, Martin Milanic, Sebastian Ordyniak, Sukanya Pandey, Ondrej Suchý
2023 J jnl
Treewidth is NP-Complete on Cubic Graphs (and related results).
CoRR
Hans L. Bodlaender, Édouard Bonnet, Lars Jaffke, Dusan Knop, Paloma T. Lima, Martin Milanic, Sebastian Ordyniak, Sukanya Pandey, Ondrej Suchý
2023 J jnl
Typical Sequences Revisited - Computing Width Parameters of Graphs.
Theory Comput. Syst.
Hans L. Bodlaender, Lars Jaffke, Jan Arne Telle
2022 A conf
A Unifying Framework for Characterizing and Computing Width Measures.
ITCS
Eduard Eiben, Robert Ganian, Thekla Hamm, Lars Jaffke, O-joung Kwon
2022 J jnl
A logic-based algorithmic meta-theorem for mim-width.
CoRR
Benjamin Bergougnoux, Jan Dreier, Lars Jaffke
2022 J jnl
A tight quasi-polynomial bound for Global Label Min-Cut.
CoRR
Lars Jaffke, Paloma T. Lima, Tomás Masarík, Marcin Pilipczuk, Uéverton S. Souza
2022 A conf
Classes of Intersection Digraphs with Good Algorithmic Properties.
STACS
Lars Jaffke, O-joung Kwon, Jan Arne Telle
2022 J jnl
Diversity of solutions: An exploration through the lens of fixed-parameter tractability theory.
Artif. Intell.
Julien Baste, Michael R. Fellows, Lars Jaffke, Tomás Masarík, Mateus de Oliveira Oliveira, Geevarghese Philip, Frances A. Rosamond
2022 J jnl
Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation.
CoRR
Meike Hatzel, Lars Jaffke, Paloma T. Lima, Tomás Masarík, Marcin Pilipczuk, Roohani Sharma, Manuel Sorge
2022 B conf
On the Hardness of Generalized Domination Problems Parameterized by Mim-Width.
IPEC
Brage I. K. Bakkane, Lars Jaffke
2022 J jnl
Structural Parameterizations of Clique Coloring.
Algorithmica
Lars Jaffke, Paloma T. Lima, Geevarghese Philip
2022 A conf
Taming Graphs with No Large Creatures and Skinny Ladders.
ESA
Jakub Gajarský, Lars Jaffke, Paloma T. Lima, Jana Novotná, Marcin Pilipczuk, Pawel Rzazewski, Uéverton S. Souza
2022 J jnl
Taming graphs with no large creatures and skinny ladders.
CoRR
Jakub Gajarský, Lars Jaffke, Paloma T. Lima, Jana Novotná, Marcin Pilipczuk, Pawel Rzazewski, Uéverton S. Souza
2022 J jnl
Well-partitioned chordal graphs.
Discret. Math.
Jungho Ahn, Lars Jaffke, O-joung Kwon, Paloma T. Lima
2022 B conf
XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure.
IPEC
Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Lars Jaffke, Paloma T. Lima
2022 J jnl
b-Coloring Parameterized by Pathwidth is XNLP-complete.
CoRR
Lars Jaffke, Paloma T. Lima, Roohani Sharma
2021 J jnl
A Unifying Framework for Characterizing and Computing Width Measures.
CoRR
Eduard Eiben, Robert Ganian, Thekla Hamm, Lars Jaffke, O-joung Kwon
2021 J jnl
Classes of intersection digraphs with good algorithmic properties.
CoRR
Lars Jaffke, O-joung Kwon, Jan Arne Telle
2021 C conf
Three Problems on Well-Partitioned Chordal Graphs.
CIAC
Jungho Ahn, Lars Jaffke, O-joung Kwon, Paloma T. Lima
2021 A conf
b-Coloring Parameterized by Clique-Width.
STACS
Lars Jaffke, Paloma T. Lima, Daniel Lokshtanov
2020 J jnl
A complexity dichotomy for critical values of the
Theor. Comput. Sci.
Lars Jaffke, Paloma T. Lima
2020 B conf
Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach.
MFCS
Lars Jaffke, Mateus de Oliveira Oliveira, Hans Raj Tiwary
2020 J jnl
Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach.
CoRR
Lars Jaffke, Mateus de Oliveira Oliveira, Hans Raj Tiwary
2020 B conf
Diverse Pairs of Matchings.
ISAAC
Fedor V. Fomin, Petr A. Golovach, Lars Jaffke, Geevarghese Philip, Danil Sagunov
2020 J jnl
Diverse Pairs of Matchings.
CoRR
Fedor V. Fomin, Petr A. Golovach, Lars Jaffke, Geevarghese Philip, Danil Sagunov
2020 A* conf
Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory.
IJCAI
Julien Baste, Michael R. Fellows, Lars Jaffke, Tomás Masarík, Mateus de Oliveira Oliveira, Geevarghese Philip, Frances A. Rosamond
2020 A conf
Hedonic Seat Arrangement Problems.
AAMAS
Hans L. Bodlaender, Tesshu Hanaka, Lars Jaffke, Hirotaka Ono, Yota Otachi, Tom C. van der Zanden
2020 J jnl
Hedonic Seat Arrangement Problems.
CoRR
Hans L. Bodlaender, Tesshu Hanaka, Lars Jaffke, Hirotaka Ono, Yota Otachi, Tom C. van der Zanden
2020 J jnl
Mim-Width I. Induced path problems.
Discret. Appl. Math.
Lars Jaffke, O-joung Kwon, Jan Arne Telle
2020 J jnl
Mim-Width II. The Feedback Vertex Set Problem.
Algorithmica
Lars Jaffke, O-joung Kwon, Jan Arne Telle
2020 B conf
Structural Parameterizations of Clique Coloring.
MFCS
Lars Jaffke, Paloma T. Lima, Geevarghese Philip
2020 J jnl
Structural Parameterizations of Clique Coloring.
CoRR
Lars Jaffke, Paloma T. Lima, Geevarghese Philip
2020 A conf
Typical Sequences Revisited - Computing Width Parameters of Graphs.
STACS
Hans L. Bodlaender, Lars Jaffke, Jan Arne Telle
2020 B conf
Well-Partitioned Chordal Graphs: Obstruction Set and Disjoint Paths.
WG
Jungho Ahn, Lars Jaffke, O-joung Kwon, Paloma T. Lima
2020 J jnl
Well-partitioned chordal graphs: obstruction set and disjoint paths.
CoRR
Jungho Ahn, Lars Jaffke, O-joung Kwon, Paloma T. Lima
2020 J jnl
b-Coloring Parameterized by Clique-Width.
CoRR
Lars Jaffke, Paloma T. Lima, Daniel Lokshtanov
2019 B conf
A Complexity Dichotomy for Critical Values of the b-Chromatic Number of Graphs.
MFCS
Lars Jaffke, Paloma T. Lima
2019 J jnl
Diversity in Combinatorial Optimization.
CoRR
Julien Baste, Michael R. Fellows, Lars Jaffke, Tomás Masarík, Mateus de Oliveira Oliveira, Geevarghese Philip, Frances A. Rosamond
2019 J jnl
FPT Algorithms for Diverse Collections of Hitting Sets.
Algorithms
Julien Baste, Lars Jaffke, Tomás Masarík, Geevarghese Philip, Günter Rote
2019 J jnl
FPT Algorithms for Diverse Collections of Hitting Sets.
CoRR
Julien Baste, Lars Jaffke, Tomás Masarík, Geevarghese Philip, Günter Rote
2019 J jnl
Mim-width III. Graph powers and generalized distance domination problems.
Theor. Comput. Sci.
Lars Jaffke, O-joung Kwon, Torstein J. F. Strømme, Jan Arne Telle
2019 J jnl
Typical Sequences Revisited - Algorithms for Linear Orderings of Series Parallel Digraphs.
CoRR
Hans L. Bodlaender, Lars Jaffke, Jan Arne Telle
2018 J jnl
A Complexity Dichotomy for Critical Values of the b-Chromatic Number of Graphs.
CoRR
Lars Jaffke, Paloma T. Lima
2018 A conf
A Unified Polynomial-Time Algorithm for Feedback Vertex Set on Graphs of Bounded Mim-Width.
STACS
Lars Jaffke, O-joung Kwon, Jan Arne Telle
2018 B conf
Generalized Distance Domination Problems and Their Complexity on Graphs of Bounded mim-width.
IPEC
Lars Jaffke, O-joung Kwon, Torstein J. F. Strømme, Jan Arne Telle
2018 J jnl
Generalized distance domination problems and their complexity on graphs of bounded mim-width.
CoRR
Lars Jaffke, O-joung Kwon, Torstein J. F. Strømme, Jan Arne Telle
2018 B conf
On Weak Isomorphism of Rooted Vertex-Colored Graphs.
WG
Lars Jaffke, Mateus de Oliveira Oliveira
2018 — conf
What Is Known About Vertex Cover Kernelization?
Adventures Between Lower Bounds and Higher Altitudes
Michael R. Fellows, Lars Jaffke, Aliz Izabella Király, Frances A. Rosamond, Mathias Weller
2018 J jnl
What is known about Vertex Cover Kernelization?
CoRR
Michael R. Fellows, Lars Jaffke, Aliz Izabella Király, Frances A. Rosamond, Mathias Weller
2017 J jnl
A note on the complexity of Feedback Vertex Set parameterized by mim-width.
CoRR
Lars Jaffke, O-joung Kwon, Jan Arne Telle
2017 J jnl
A unified polynomial-time algorithm for Feedback Vertex Set on graphs of bounded mim-width.
CoRR
Lars Jaffke, O-joung Kwon, Jan Arne Telle
2017 J jnl
Definability equals recognizability for k-outerplanar graphs and l-chordal partial k-trees.
Eur. J. Comb.
Lars Jaffke, Hans L. Bodlaender, Pinar Heggernes, Jan Arne Telle
2017 C conf
Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems.
CIAC
Lars Jaffke, Bart M. P. Jansen
2017 J jnl
Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems.
CoRR
Lars Jaffke, Bart M. P. Jansen
2017 B conf
Polynomial-Time Algorithms for the Longest Induced Path and Induced Disjoint Paths Problems on Graphs of Bounded Mim-Width.
IPEC
Lars Jaffke, O-joung Kwon, Jan Arne Telle
2017 J jnl
Polynomial-time algorithms for the Longest Induced Path and Induced Disjoint Paths problems on graphs of bounded mim-width.
CoRR
Lars Jaffke, O-joung Kwon, Jan Arne Telle
2015 J jnl
Definability Equals Recognizability for $k$-Outerplanar Graphs.
CoRR
Lars Jaffke, Hans L. Bodlaender
2015 B conf
Definability Equals Recognizability for k-Outerplanar Graphs.
IPEC
Lars Jaffke, Hans L. Bodlaender
2015 J jnl
MSOL-Definability Equals Recognizability for Halin Graphs and Bounded Degree k-Outerplanar Graphs.
CoRR
Lars Jaffke, Hans L. Bodlaender