7 citations · 18 across the 11 of their papers we have counts for
11 papers
Enumerating Connected Dominating Sets
Faisal Abu-Khzam, Henning Fernau, Benjamin Gras +2
The question to enumerate all inclusion-minimal connected dominating sets in a graph of order in time significantly less than is an open question that was asked in many p…
Fixing improper colorings of graphs
Valentin Garnero, Konstanty Junosza-Szaniawski, Mathieu Liedloff +2
In this paper we consider a variation of a recoloring problem, called the Color-Fixing. Let us have some non-proper -coloring of a graph . We investigate the problem of f…
Algorithmic Aspects of Upper Domination
Cristina Bazgan, Ljiljana Brankovic, Katrin Casel +6
In this paper we study combinatorial and algorithmic resp. complexity questions of upper domination, i.e., the maximum cardinality of a minimal dominating set in a graph. We give a…
Algorithms parameterized by vertex cover and modular width, through potential maximal cliques
Fedor V. Fomin, Mathieu Liedloff, Pedro Montealegre +1
In this paper we give upper bounds on the number of minimal separators and potential maximal cliques of graphs w.r.t. two graph parameters, namely vertex cover (…
TREEWIDTH and PATHWIDTH parameterized by vertex cover
Mathieu Chapelle, Mathieu Liedloff, Ioan Todinca +1
After the number of vertices, Vertex Cover is the largest of the classical graph parameters and has more and more frequently been used as a separate parameter in parameterized prob…
On Finding Optimal Polytrees
Serge Gaspers, Mikko Koivisto, Mathieu Liedloff +2
Inferring probabilistic networks from data is a notoriously difficult task. Under various goodness-of-fit measures, finding an optimal network is NP-hard, even if restricted to pol…