13 citations · 46 across the 31 of their papers we have counts for
5 papers · 2 filters
Maximum Independent Sets in Subcubic Graphs: New Results
Ararat Harutyunyan, Michael Lampis, Vadim Lozin +1
The maximum independent set problem is known to be NP-hard in the class of subcubic graphs, i.e. graphs of vertex degree at most 3. We present a polynomial-time solution in a subcl…
Token Sliding on Split Graphs
Rémy Belmonte, Eun Jung Kim, Michael Lampis +3
We consider the complexity of the Independent Set Reconfiguration problem under the Token Sliding rule. In this problem we are given two independent sets of a graph and are asked i…
How Bad is the Freedom to Flood-It?
Rémy Belmonte, Mehdi Khosravian Ghadikolaei, Masashi Kiyomi +2
Fixed-Flood-It and Free-Flood-It are combinatorial problems on graphs that generalize a very popular puzzle called Flood-It. Both problems consist of recoloring moves whose goal is…
Parameterized (Approximate) Defective Coloring
Rémy Belmonte, Michael Lampis, Valia Mitsou
In Defective Coloring we are given a graph and two integers and are asked if we can partition into color classes, so that each class induces a gra…
Parameterized Power Vertex Cover
Eric Angel, Evripidis Bampis, Bruno Escoffier +1
We study a recently introduced generalization of the Vertex Cover (VC) problem, called Power Vertex Cover (PVC). In this problem, each edge of the input graph is supplied with a po…