Lars Jaffke

Lars Jaffke

Theoretical Computer Scientist

About Me

I am a PhD Student in (Multivariate) Algorithmics in the algorithms group at the University of Bergen. My advisors are Michael Fellows and Jan Arne Telle. My main research interests revolve around graphs in algorithms.

Recent Manuscripts

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

with Hans L. Bodlaender and Jan Arne Telle
preprint (2019)
arXiv

Diversity in Combinatorial Optimization

with Julien Baste, Michael R. Fellows, Tomáš Masařík, Mateus de Oliveira Oliveira, Geevarghese Philip, and Frances A. Rosamond
preprint (2019)
arXiv

Journal Articles

Mim-Width III. Graph Powers and Generalized Distance Domination Problems

with O-joung Kwon, Torstein J. F. Strømme, and Jan Arne Telle
Theoretical Computer Science (online, 2019) [pdf]

Mim-Width II. The Feedback Vertex Set Problem

with O-joung Kwon and Jan Arne Telle
Algorithmica (online, 2019) [pdf]

Definability Equals Recognizability for k-Outerplanar Graphs and l-Chordal Partial k-Trees

with Hans L. Bodlaender, Pinar Heggernes, and Jan Arne Telle
European Journal of Combinatorics 66:191-234 (2017) bibtex

Conference Proceedings and Collections

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

with Paloma T. Lima
MFCS 2019, LIPIcs 138: 34:1-34:13 arXiv bibtex

Generalized Distance Domination Problems and Their Complexity on Graphs of Bounded Mim-Width

with O-joung Kwon, Torstein J. F. Strømme, and Jan Arne Telle
IPEC 2018, LIPIcs 115: 6:1-6:14 arXiv bibtex

On Weak Isomorphism of Rooted Vertex-Colored Graphs

with Mateus de Oliveira Oliveira
WG 2018, LNCS 11159: 266-278 bibtex

What is known about Vertex Cover Kernelization?

with Michael R. Fellows, Aliz Kiraly, Frances A. Rosamond, and Mathias Weller
LNCS 11011: 330-356 (2018) arXiv bibtex
Note: The arXiv-version fixes a flaw in Redcuction R.8 of the LNCS version.

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

with O-joung Kwon and Jan Arne Telle
STACS 2018, LIPIcs 96: 41:1-42:14 arXiv bibtex

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

with O-joung Kwon and Jan Arne Telle
IPEC 2017, LIPIcs 89: 21:1-21:13 arXiv bibtex

Fine-Grained Parameterized Complexity Analysis of Graph Coloring Problems

with Bart M. P. Jansen
CIAC 2017, LNCS 10236: 345-356 arXiv bibtex

Definability Equals Recognizability for k-Outerplanar Graphs

with Hans L. Bodlaender
IPEC 2015, LIPIcs 43: 175-186 bibtex

Notes

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

with O-joung Kwon and Jan Arne Telle
arXiv (2017) bibtex