Lars Jaffke

Publication Activity (10 Years)

Years Active: 2015-2024
Publications (10 Years): 65

Top Topics

Tree Decompositions

Graph Coloring Problems

Top Venues

Publications

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