Lars Jaffke

Postdoctoral Fellow

E-maillars.jaffke@uib.no
Visitor Address
HIB - Thormøhlens gate 55

5006 Bergen
Postal Address
Postboks 7803

5020 Bergen

Research
Publications

Most of my research lies in the intersection of algorithmic graph theory --- with a focus on graph decompositions and width paramters --- and parameterized algorithms and complexity.

Academic article

Show author(s) (2023). b-Coloring Parameterized by Clique-Width. Theory of Computing Systems. 33 pages.
Show author(s) (2023). Treewidth is NP-Complete on Cubic Graphs. Leibniz International Proceedings in Informatics. 7:1-7:13.
Show author(s) (2023). Structural Parameterizations of b-Coloring. Leibniz International Proceedings in Informatics. 40:1-40:14.
Show author(s) (2023). On the maximum number of edges in planar graphs of bounded degree and matching number. Discrete Mathematics. 7 pages.
Show author(s) (2023). Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation. Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms. 3229-3244.
Show author(s) (2023). Fine-grained parameterized complexity analysis of graph coloring problems. Discrete Applied Mathematics. 33-46.
Show author(s) (2023). Dynamic Programming on Bipartite Tree Decompositions. Leibniz International Proceedings in Informatics. 26:1-26:22.
Show author(s) (2023). Classes of intersection digraphs with good algorithmic properties. Journal of Graph Theory. 39 pages.
Show author(s) (2023). A tight quasi-polynomial bound for Global Label Min-Cut. Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms. 290-303.
Show author(s) (2023). A logic-based algorithmic meta-theorem for mim-width. Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms. 3282-3304.

Show author(s) (2022). XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure. Leibniz International Proceedings in Informatics. 8:1-8:18.
Show author(s) (2022). Well-partitioned chordal graphs. Discrete Mathematics. 23 pages.
Show author(s) (2022). Taming Graphs with No Large Creatures and Skinny Ladders. Leibniz International Proceedings in Informatics. 58:1-58:8.
Show author(s) (2022). On the Hardness of Generalized Domination Problems Parameterized by Mim-Width. Leibniz International Proceedings in Informatics. 3:1-3:19.
Show author(s) (2022). Diversity of solutions: An exploration through the lens of fixed-parameter tractability theory. Artificial Intelligence. 15 pages.
Show author(s) (2022). Classes of Intersection Digraphs with Good Algorithmic Properties. Leibniz International Proceedings in Informatics. 38:1-38:18.
Show author(s) (2022). A Unifying Framework for Characterizing and Computing Width Measures. Leibniz International Proceedings in Informatics. 63:1-63:23.

Show author(s) (2021). b-Coloring Parameterized by Clique-Width. Leibniz International Proceedings in Informatics. 43:1-43:15.
Show author(s) (2021). Typical Sequences Revisited -- Computing Width Parameters of Graphs. Theory of Computing Systems. 37 pages.
Show author(s) (2021). Three problems on well-partitioned chordal graphs. Lecture Notes in Computer Science (LNCS). 23-36.
Show author(s) (2021). Structural Parameterizations of Clique Coloring. Algorithmica. 1-31.

Show author(s) (2020). Typical Sequences Revisited - Computing Width Parameters of Graphs. Leibniz International Proceedings in Informatics. 57:1-57:16.
Show author(s) (2020). Mim-Width II. The Feedback Vertex Set Problem. Algorithmica. 118-145.
Show author(s) (2020). Hedonic Seat Arrangement Problems. Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS. 1777-1779.
Show author(s) (2020). Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory. IJCAI International Joint Conference on Artificial Intelligence. 1119-1125.
Show author(s) (2020). Diverse Pairs of Matchings. Leibniz International Proceedings in Informatics. 26:1-26:12.
Show author(s) (2020). Compressing permutation groups into grammars and polytopes. A graph embedding approach. Leibniz International Proceedings in Informatics. 50:1-50:15.
Show author(s) (2020). A complexity dichotomy for critical values of the b-chromatic number of graphs. Theoretical Computer Science. 182-196.

Show author(s) (2019). Mim-Width III. Graph powers and generalized distance domination problems. Theoretical Computer Science. 216-236.
Show author(s) (2019). Mim-Width I. Induced Path Problems. Discrete Applied Mathematics.
Show author(s) (2019). Generalized distance domination problems and their complexity on graphs of bounded mim-width. Leibniz International Proceedings in Informatics.
Show author(s) (2019). FPT Algorithms for Diverse Collections of Hitting Sets. Algorithms. 18 pages.
Show author(s) (2019). A complexity dichotomy for critical values of the b-chromatic number of graphs. Leibniz International Proceedings in Informatics. 34:1-34:13.

Show author(s) (2018). What Is Known About Vertex Cover Kernelization? Lecture Notes in Computer Science (LNCS). 330-356.
Show author(s) (2018). Polynomial-time algorithms for the Longest Induced Path and Induced Disjoint Paths problems on graphs of bounded mim-width. Leibniz International Proceedings in Informatics. 1-13.
Show author(s) (2018). On weak isomorphism of rooted vertex-colored graphs. Lecture Notes in Computer Science (LNCS). 266-278.
Show author(s) (2018). A Unified Polynomial-Time Algorithm for Feedback Vertex Set on Graphs of Bounded Mim-Width. Leibniz International Proceedings in Informatics. 42:1-42:14.

Show author(s) (2017). Fine-grained parameterized complexity analysis of graph coloring problems. Lecture Notes in Computer Science (LNCS). 345-356.
Show author(s) (2017). Definability equals recognizability for k-outerplanar graphs and l-chordal partial k-trees. European journal of combinatorics (Print). 191-234.

Academic lecture

Show author(s) (2021). Diversity of Solutions: An Exploration Through the Lens of Fixed-Parameter Tractability Theory.

Academic chapter/article/Conference paper

Show author(s) (2020). Well-Partitioned Chordal Graphs: Obstruction Set and Disjoint Paths. 13 pages.

More information in national current research information system (CRIStin)

Fields of competence

Algorithms

Discrete Mathematics

Graph Theory

Parameterized Complexity