|
|
|
|
|
Wenjun Li, Xueying Yang, Chao Xu and Yongjie Yang
In the directed co-graph edge-deletion problem, we are given a directed graph and an integer k, and the question is whether we can delete, at most, k edges so that the resulting graph is a directed co-graph. In this paper, we make two minor contributions...
ver más
|
|
|
|
|
|
|
|
|
|
|
Max Bannach and Till Tantau
Color coding is an algorithmic technique used in parameterized complexity theory to detect ?small? structures inside graphs. The idea is to derandomize algorithms that first randomly color a graph and then search for an easily-detectable, small color pat...
ver más
|
|
|
|
|
|
|
|
|
|
|
Julien Baste, Lars Jaffke, Tomá? Masarík, Geevarghese Philip and Günter Rote
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 parameterized complexity. This paradig...
ver más
|
|
|
|
|
|
|
|
|
|
|
Nadia Creignou, Raïda Ktari, Arne Meier, Julian-Steffen Müller, Frédéric Olive and Heribert Vollmer
Recently, Creignou et al. (Theory Comput. Syst. 2017), introduced the class DelayFPT into parameterised complexity theory in order to capture the notion of efficiently solvable parameterised enumeration problems. In this paper, we propose a framework for...
ver más
|
|
|
|
|
|
|
|
|
|
|
Wenxing Lai
Chen and Flum showed that any FPT-approximation of the k-Clique problem is not in para-??????
AC
0
and the k-DominatingSet (k-DomSet) problem could not be computed by para-??????
AC
0
circuits. It is natural to ask whether the ??(??)
f
(
k
)
-approxima...
ver más
|
|
|
|
|
|