54 citations · 152 across the 16 of their papers we have counts for
7 papers · 1 filter
Grundy Coloring & friends, Half-Graphs, Bicliques
Pierre Aboulker, Édouard Bonnet, Eun Jung Kim +1
The first-fit coloring is a heuristic that assigns to each vertex, arriving in a specified order , the smallest available color. The problem Grundy Coloring asks how many colors…
Extension of vertex cover and independent set in some classes of graphs and generalizations
Katrin Casel, Henning Fernau, Mehdi Khosravian Ghadikolaei +2
We consider extension variants of the classical graph problems Vertex Cover and Independent Set. Given a graph and a vertex set , it is asked if there exis…
On the Complexity of Solution Extension of Optimization Problems
Katrin Casel, Henning Fernau, Mehdi Khosravian Ghadikolaei +2
The question if a given partial solution to a problem can be extended reasonably occurs in many algorithmic approaches for optimization problems. For instance, when enumerating min…
Parameterized Orientable Deletion
Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis +2
A graph is -orientable if its edges can be oriented so that the maximum in-degree of the resulting digraph is at most . -orientability is a well-studied concept with close…
Parameterized Inapproximability of Target Set Selection and Generalizations
Cristina Bazgan, Morgan Chopin, André Nichterlein +1
In this paper, we consider the Target Set Selection problem: given a graph and a threshold value for any vertex of the graph, find a minimum size vertex-subset to "act…
Some results on more flexible versions of Graph Motif
Romeo Rizzi, Florian Sikora
The problems studied in this paper originate from Graph Motif, a problem introduced in 2006 in the context of biological networks. Informally speaking, it consists in deciding if a…
Finding and counting vertex-colored subtrees
Sylvain Guillemot, Florian Sikora
The problems studied in this article originate from the Graph Motif problem introduced by Lacroix et al. in the context of biological networks. The problem is to decide if a vertex…