M. Lampis

activity

20092026

most citedModel Checking Lower Bounds for Simple Graphs

13 citations · 46 across the 31 of their papers we have counts for

collaborators

Showing 2020Show all

3 papers · 1 filter

cs.CC2020

Digraph Coloring and Distance to Acyclicity

Ararat Harutyunyan, Michael Lampis, Nikolaos Melissinos

In $k$ -Digraph Coloring we are given a digraph and are asked to partition its vertices into at most $k$ sets, so that each set induces a DAG. This well-known problem is NP-hard, as…

cs.DS2020

Parameterized Complexity of $(A, ℓ)$ -Path Packing

Rémy Belmonte, Tesshu Hanaka, Masaaki Kanzaki +6

Given a graph $G = (V, E)$ , $A \subseteq V$ , and integers $k$ and $ℓ$ , the \textsc{ $(A, ℓ)$ -Path Packing} problem asks to find $k$ vertex-disjoint paths of length $ℓ$ that h…

cs.DS2020★ 3 cited

Grundy Distinguishes Treewidth from Pathwidth

Rémy Belmonte, Eun Jung Kim, Michael Lampis +2

Structural graph parameters, such as treewidth, pathwidth, and clique-width, are a central topic of study in parameterized complexity. A main aim of research in this area is to und…

Digraph Coloring and Distance to Acyclicity

Parameterized Complexity of (A,ℓ)-Path Packing

Grundy Distinguishes Treewidth from Pathwidth

Parameterized Complexity of $(A, ℓ)$ -Path Packing