|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
Neeldhara Misra, Frances Rosamond and Meirav Zehavi
This Special Issue contains eleven articles?surveys and research papers?that represent fresh and ambitious new directions in the area of Parameterized Complexity. They provide ground-breaking research at the frontiers of knowledge, and they contribute to...
ver más
|
|
|
|
|
|
|
|
|
|
|
Arne Meier
In this paper, we study the relationship of parameterized enumeration complexity classes defined by Creignou et al. (MFCS 2013). Specifically, we introduce two hierarchies (IncFPTa and CapIncFPTa) of enumeration complexity classes for incremental fpt-tim...
ver más
|
|
|
|
|
|
|
|
|
|
|
N. S. Narayanaswamy and R. Vijayaragunathan
We present a detailed survey of results and two new results on graphical models of uncertainty and associated optimization problems. We focus on two well-studied models, namely, the Random Failure (RF) model and the Linear Reliability Ordering (LRO) mode...
ver más
|
|
|
|
|
|
|
|
|
|
|
Ronald de Haan and Stefan Szeider
We present a list of parameterized problems together with a complexity classification of whether they allow a fixed-parameter tractable reduction to SAT or not. These problems are parameterized versions of problems whose complexity lies at the second lev...
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
|
|
|
|
|
|
|
|
|
|
|
Nguyen Uyen Thuong DOI: 10.26459/hueuni-jed.v128i5C.5121
Pág. 67?80
Abstract: The world, nowadays, is closer and closer thanks to information communication technology (ICT). Actually, virtual teams are considered as a great way to connect people and bring advantages to organizations. From the existing literature, it is e...
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
|
|
|
|
|
|