Lars Jaffke

According to our database, Lars Jaffke authored at least 42 papers between 2015 and 2023.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2023

On the maximum number of edges in planar graphs of bounded degree and matching number.

Lars Jaffke, Paloma T. Lima

Discret. Math., August, 2023

Typical Sequences Revisited - Computing Width Parameters of Graphs.

Hans L. Bodlaender, Lars Jaffke, Jan Arne Telle

Theory Comput. Syst., February, 2023

Fine-grained parameterized complexity analysis of graph coloring problems.

Lars Jaffke, Bart M. P. Jansen

Discret. Appl. Math., 2023

Treewidth is NP-Complete on Cubic Graphs (and related results).

Hans L. Bodlaender, Édouard Bonnet, Lars Jaffke, Dusan Knop, Paloma T. Lima, Martin Milanic, Sebastian Ordyniak, Sukanya Pandey, Ondrej Suchý

CoRR, 2023

A tight quasi-polynomial bound for Global Label Min-Cut.

Lars Jaffke, Paloma T. Lima, Tomás Masarík, Marcin Pilipczuk, Uéverton S. Souza

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation.

Meike Hatzel, Lars Jaffke, Paloma T. Lima, Tomás Masarík, Marcin Pilipczuk, Roohani Sharma, Manuel Sorge

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

A logic-based algorithmic meta-theorem for mim-width.

Benjamin Bergougnoux, Jan Dreier, Lars Jaffke

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Dynamic Programming on Bipartite Tree Decompositions.

Lars Jaffke, Laure Morelle, Ignasi Sau, Dimitrios M. Thilikos

Proceedings of the 18th International Symposium on Parameterized and Exact Computation, 2023

Treewidth Is NP-Complete on Cubic Graphs.

Hans L. Bodlaender, Édouard Bonnet, Lars Jaffke, Dusan Knop, Paloma T. Lima, Martin Milanic, Sebastian Ordyniak, Sukanya Pandey, Ondrej Suchý

Proceedings of the 18th International Symposium on Parameterized and Exact Computation, 2023

Structural Parameterizations of b-Coloring.

Lars Jaffke, Paloma T. Lima, Roohani Sharma

Proceedings of the 34th International Symposium on Algorithms and Computation, 2023

2022

Well-partitioned chordal graphs.

Jungho Ahn, Lars Jaffke, O-joung Kwon, Paloma T. Lima

Discret. Math., 2022

b-Coloring Parameterized by Pathwidth is XNLP-complete.

Lars Jaffke, Paloma T. Lima, Roohani Sharma

CoRR, 2022

Structural Parameterizations of Clique Coloring.

Lars Jaffke, Paloma T. Lima, Geevarghese Philip

Algorithmica, 2022

Diversity of solutions: An exploration through the lens of fixed-parameter tractability theory.

Julien Baste, Michael R. Fellows, Lars Jaffke, Tomás Masarík, Mateus de Oliveira Oliveira, Geevarghese Philip, Frances A. Rosamond

Artif. Intell., 2022

Classes of Intersection Digraphs with Good Algorithmic Properties.

Lars Jaffke, O-joung Kwon, Jan Arne Telle

Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science, 2022

XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure.

Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Lars Jaffke, Paloma T. Lima

Proceedings of the 17th International Symposium on Parameterized and Exact Computation, 2022

On the Hardness of Generalized Domination Problems Parameterized by Mim-Width.

Brage I. K. Bakkane, Lars Jaffke

Proceedings of the 17th International Symposium on Parameterized and Exact Computation, 2022

A Unifying Framework for Characterizing and Computing Width Measures.

Eduard Eiben, Robert Ganian, Thekla Hamm, Lars Jaffke, O-joung Kwon

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Taming Graphs with No Large Creatures and Skinny Ladders.

Jakub Gajarský, Lars Jaffke, Paloma T. Lima, Jana Novotná, Marcin Pilipczuk, Pawel Rzazewski, Uéverton S. Souza

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

2021

b-Coloring Parameterized by Clique-Width.

Lars Jaffke, Paloma T. Lima, Daniel Lokshtanov

Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science, 2021

Three Problems on Well-Partitioned Chordal Graphs.

Jungho Ahn, Lars Jaffke, O-joung Kwon, Paloma T. Lima

Proceedings of the Algorithms and Complexity - 12th International Conference, 2021

2020

A complexity dichotomy for critical values of the <i>b</i>-chromatic number of graphs.

Lars Jaffke, Paloma T. Lima

Theor. Comput. Sci., 2020

Mim-Width I. Induced path problems.

Lars Jaffke, O-joung Kwon, Jan Arne Telle

Discret. Appl. Math., 2020

Mim-Width II. The Feedback Vertex Set Problem.

Lars Jaffke, O-joung Kwon, Jan Arne Telle

Algorithmica, 2020

Well-Partitioned Chordal Graphs: Obstruction Set and Disjoint Paths.

Jungho Ahn, Lars Jaffke, O-joung Kwon, Paloma T. Lima

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2020

Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach.

Lars Jaffke, Mateus de Oliveira Oliveira, Hans Raj Tiwary

Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, 2020

Diverse Pairs of Matchings.

Fedor V. Fomin, Petr A. Golovach, Lars Jaffke, Geevarghese Philip, Danil Sagunov

Proceedings of the 31st International Symposium on Algorithms and Computation, 2020

Hedonic Seat Arrangement Problems.

Hans L. Bodlaender, Tesshu Hanaka, Lars Jaffke, Hirotaka Ono, Yota Otachi, Tom C. van der Zanden

Proceedings of the 19th International Conference on Autonomous Agents and Multiagent Systems, 2020

2019

Mim-width III. Graph powers and generalized distance domination problems.

Lars Jaffke, O-joung Kwon, Torstein J. F. Strømme, Jan Arne Telle

Theor. Comput. Sci., 2019

Typical Sequences Revisited - Algorithms for Linear Orderings of Series Parallel Digraphs.

Hans L. Bodlaender, Lars Jaffke, Jan Arne Telle

CoRR, 2019

Diversity in Combinatorial Optimization.

Julien Baste, Michael R. Fellows, Lars Jaffke, Tomás Masarík, Mateus de Oliveira Oliveira, Geevarghese Philip, Frances A. Rosamond

CoRR, 2019

FPT Algorithms for Diverse Collections of Hitting Sets.

Julien Baste, Lars Jaffke, Tomás Masarík, Geevarghese Philip, Günter Rote

Algorithms, 2019

A Complexity Dichotomy for Critical Values of the b-Chromatic Number of Graphs.

Lars Jaffke, Paloma T. Lima

Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019

2018

On Weak Isomorphism of Rooted Vertex-Colored Graphs.

Lars Jaffke, Mateus de Oliveira Oliveira

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2018

A Unified Polynomial-Time Algorithm for Feedback Vertex Set on Graphs of Bounded Mim-Width.

Lars Jaffke, O-joung Kwon, Jan Arne Telle

Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, 2018

Generalized Distance Domination Problems and Their Complexity on Graphs of Bounded mim-width.

Lars Jaffke, O-joung Kwon, Torstein J. F. Strømme, Jan Arne Telle

Proceedings of the 13th International Symposium on Parameterized and Exact Computation, 2018

What Is Known About Vertex Cover Kernelization?

Michael R. Fellows, Lars Jaffke, Aliz Izabella Király, Frances A. Rosamond, Mathias Weller

Proceedings of the Adventures Between Lower Bounds and Higher Altitudes, 2018

2017

Definability equals recognizability for k-outerplanar graphs and l-chordal partial k-trees.

Lars Jaffke, Hans L. Bodlaender, Pinar Heggernes, Jan Arne Telle

Eur. J. Comb., 2017

A note on the complexity of Feedback Vertex Set parameterized by mim-width.

Lars Jaffke, O-joung Kwon, Jan Arne Telle

CoRR, 2017

Polynomial-Time Algorithms for the Longest Induced Path and Induced Disjoint Paths Problems on Graphs of Bounded Mim-Width.

Lars Jaffke, O-joung Kwon, Jan Arne Telle

Proceedings of the 12th International Symposium on Parameterized and Exact Computation, 2017

2015

MSOL-Definability Equals Recognizability for Halin Graphs and Bounded Degree k-Outerplanar Graphs.

Lars Jaffke, Hans L. Bodlaender

CoRR, 2015

Definability Equals Recognizability for k-Outerplanar Graphs.

Lars Jaffke, Hans L. Bodlaender

Proceedings of the 10th International Symposium on Parameterized and Exact Computation, 2015