Blar i Department of Informatics på forfatter "Jaffke, Lars"

Viser treff 1-20 av 27

    • b-Coloring Parameterized by Clique-Width 

      Jaffke, Lars; Lima, Paloma Thome de; Lokshtanov, Daniel (Journal article; Peer reviewed, 2021)
      We provide a polynomial-time algorithm for b-Coloring on graphs of constant clique-width. This unifies and extends nearly all previously known polynomial-time results on graph classes, and answers open questions posed by ...

    • b-Coloring Parameterized by Clique-Width 

      Jaffke, Lars; Lima, Paloma T.; Lokshtanov, Daniel (Journal article; Peer reviewed, 2023)
      We provide a polynomial-time algorithm for b- Coloring on graphs of constant clique-width. This unifies and extends nearly all previously known polynomial time results on graph classes, and answers open questions posed by ...

    • Classes of Intersection Digraphs with Good Algorithmic Properties 

      Jaffke, Lars; Kwon, O-joung; Telle, Jan Arne (Journal article; Peer reviewed, 2022)
      While intersection graphs play a central role in the algorithmic analysis of hard problems on undirected graphs, the role of intersection digraphs in algorithms is much less understood. We present several contributions ...

    • Classes of intersection digraphs with good algorithmic properties 

      Jaffke, Lars; Kwon, O-joung; Telle, Jan Arne (Journal article; Peer reviewed, 2023)
      While intersection graphs play a central role in the algorithmic analysis of hard problems on undirected graphs, the role of intersection digraphs in algorithms is much less understood. We present several contributions ...

    • A complexity dichotomy for critical values of the b-chromatic number of graphs 

      Lima, Paloma T.; Jaffke, Lars (Journal article; Peer reviewed, 2020)
      A b-coloring of a graph G is a proper coloring of its vertices such that each color class contains a vertex that has at least one neighbor in all the other color classes. The b-Coloring problem asks whether a graph G has ...

    • A complexity dichotomy for critical values of the b-chromatic number of graphs 

      Jaffke, Lars; Lima, Paloma T. (Peer reviewed; Journal article, 2019-08-20)
      A b-coloring of a graph G is a proper coloring of its vertices such that each color class contains a vertex that has at least one neighbor in all the other color classes. The b-Coloring problem asks whether a graph G has ...

    • Compressing permutation groups into grammars and polytopes. A graph embedding approach 

      Jaffke, Lars; De Oliveira Oliveira, Mateus; Tiwary, Hans Raj (Journal article; Peer reviewed, 2020)
      It can be shown that each permutation group G ⊑ 𝕊_n can be embedded, in a well defined sense, in a connected graph with O(n+|G|) vertices. Some groups, however, require much fewer vertices. For instance, 𝕊_n itself can ...

    • Diverse Pairs of Matchings 

      Fomin, Fedor; Golovach, Petr; Jaffke, Lars; Philip, Geevarghese; Sagunov, Danil (Journal article; Peer reviewed, 2020)
      We initiate the study of the Diverse Pair of (Maximum/ Perfect) Matchings problems which given a graph G and an integer k, ask whether G has two (maximum/perfect) matchings whose symmetric difference is at least k. Diverse ...

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

      Baste, Julien; Fellows, Michael Ralph; Jaffke, Lars; Masařík, Tomáš; Oliveira, Mateus De Oliveira; Philip, Geevarghese; Rosamond, Frances (Journal article; Peer reviewed, 2022)
      When modeling an application of practical relevance as an instance of a combinatorial problem X, we are often interested not merely in finding one optimal solution for that instance, but in finding a sufficiently diverse ...

    • Dynamic Programming on Bipartite Tree Decompositions 

      Jaffke, Lars; Morelle, Laure; Sau, Ignasi; Thilikos, Dimitrios M. (Journal article; Peer reviewed, 2023)
      We revisit a graph width parameter that we dub bipartite treewidth, along with its associated graph decomposition that we call bipartite tree decomposition. Bipartite treewidth can be seen as a common generalization of ...

    • Fine-grained parameterized complexity analysis of graph coloring problems 

      Jaffke, Lars; Jansen, Bart Maarten Paul (Journal article; Peer reviewed, 2023)
      The q-Coloring problem asks whether the vertices of a graph can be properly colored with q colors. In this paper we perform a fine-grained analysis of the complexity of q- Coloring with respect to a hierarchy of structural ...

    • FPT Algorithms for Diverse Collections of Hitting Sets 

      Baste, Julien; Jaffke, Lars; Masařík, Tomáš; Philip, Geevarghese; Rote, Günter (Peer reviewed; Journal article, 2019-11-27)
      In this work, we study the d-Hitting Set and Feedback Vertex Set problems through the paradigm of finding diverse collections of r solutions of size at most k each, which has recently been introduced to the field of ...

    • Mim-Width II. The Feedback Vertex Set Problem 

      Jaffke, Lars; Kwon, O-Joung; Telle, Jan Arne (Peer reviewed; Journal article, 2020)
      We give a first polynomial-time algorithm for (WEIGHTED) FEEDBACK VERTEX SET on graphs of bounded maximum induced matching width (mim-width). Explicitly, given a branch decomposition of mim-width w, we give an nO(w)-time ...

    • Mim-Width III. Graph powers and generalized distance domination problems 

      Telle, Jan Arne; Jaffke, Lars; Strømme, Torstein Jarl Fagerbakke; Kwon, O-Joung (Peer reviewed; Journal article, 2019)
      We generalize the family of (σ,ρ) problems and locally checkable vertex partition problems to their distance versions, which naturally captures well-known problems such as Distance-r Dominating Set and Distance-r Independent ...

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

      Bakkane, Brage I. K.; Jaffke, Lars (Journal article; Peer reviewed, 2022)
      For nonempty σ, ρ ⊆ ℕ, a vertex set S in a graph G is a (σ, ρ)-dominating set if for all v ∈ S, |N(v) ∩ S| ∈ σ, and for all v ∈ V(G) ⧵ S, |N(v) ∩ S| ∈ ρ. The Min/Max (σ,ρ)-Dominating Set problems ask, given a graph G and ...

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

      Jaffke, Lars; Lima, Paloma T. (Journal article; Peer reviewed, 2023)
      We determine the maximum number of edges that a planar graph can have as a function of its maximum degree and matching number.

    • Structural Parameterizations of b-Coloring 

      Jaffke, Lars; Lima, Paloma Thome de; Sharma, Roohani (Journal article; Peer reviewed, 2023)
      The b-Coloring problem, which given a graph G and an integer k asks whether G has a proper k-coloring such that each color class has a vertex adjacent to all color classes except its own, is known to be FPT parameterized ...

    • Structural parameterizations of clique coloring 

      Jaffke, Lars; Lima, Paloma T.; Philip, Geevarghese (Journal article; Peer reviewed, 2020)
      A clique coloring of a graph is an assignment of colors to its vertices such that no maximal clique is monochromatic. We initiate the study of structural parameterizations of the Clique Coloring problem which asks whether ...

    • Taming Graphs with No Large Creatures and Skinny Ladders 

      Gajarský, Jakub; Jaffke, Lars; Lima, Paloma Thome de; Novotná, Jana; Pilipczuk, Marcin; Rzążewski, Paweł; Souza, Uéverton S. (Journal article; Peer reviewed, 2022)
      We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class 𝒢 there exists a constant k such that no member of 𝒢 contains a k-creature as an induced subgraph or a k-skinny-ladder ...

    • Three problems on well-partitioned chordal graphs 

      Ahn, Jungho; Jaffke, Lars; Kwon, O-Joung; Lima, Paloma Thome de (Journal article; Peer reviewed, 2021)
      In this work, we solve three problems on well-partitioned chordal graphs. First, we show that every connected (resp., 2-connected) well-partitioned chordal graph has a vertex that intersects all longest paths (resp., longest ...