Results 41 to 50 of about 23,779 (205)
A Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy
Algorithms, 2019 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.
Ronald de Haan, Stefan Szeider
doaj +1 more source
A Brief Survey of Fixed-Parameter Parallelism
Algorithms, 2020 This paper provides an overview of the field of parameterized parallel complexity by surveying previous work in addition to presenting a few new observations and exploring potential new directions.
Faisal N. Abu-Khzam, Karam Al Kontar
doaj +1 more source
On the Parameterized Complexity of Consensus Clustering [PDF]
Theoretical Computer Science, 2011 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Martin Dörnfelder +3 more
openaire +2 more sources
The Parameterized Complexity of the Rainbow Subgraph Problem
Algorithms, 2015 The NP-hard RAINBOW SUBGRAPH problem, motivated from bioinformatics, is to find in an edge-colored graph a subgraph that contains each edge color exactly once and has at most \(k\) vertices.
Falk Hüffner +3 more
doaj +1 more source
Computation Models for Parameterized Complexity [PDF]
Mathematical Logic Quarterly, 1997 AbstractA parameterized computational problem is a set of pairs (x,k), wherekis a distinguished item called “parameter”. FPT is the class of fixed‐parameter tractable problems: for any fixed value ofk, they are solvable in time bounded by a polynomial of degree α, where α is a constant not dependent on the parameter. In order to deal with parameterized
Marco Cesati, Miriam Di Ianni
openaire +2 more sources
Parameterized Complexity of Geodetic Set
Journal of Graph Algorithms and Applications, 2022 A vertex set $S$ of a graph $G$ is geodetic if every vertex of $G$ lies on a shortest path between two vertices in $S$. Given a graph $G$ and $k \in \mathbb{N}$, the NP-hard ${\rm G{\small EODETIC}~S{ \small ET}}$ problem asks whether there is a geodetic set of size at most $k$.
Leon Kellerhals, Tomohiro Koana
openaire +4 more sources
On the parameterized complexity of red-blue points separation
Journal of Computational Geometry, 2019 We study the following geometric separation problem: Given a set $\mathcal R$ of red points and a set $\mathcal B$ of blue points in the plane, find a minimum-size set of lines that separate $\mathcal R$ from $\mathcal B$.
Edouard Bonnet +2 more
doaj +1 more source
Algorithms, 2020 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
Neeldhara Misra +2 more
doaj +1 more source
09511 Abstracts Collection – Parameterized complexity and approximation algorithms [PDF]
, 2010 From 14. 12. 2009 to 17. 12. 2009., the Dagstuhl Seminar 09511 ``Parameterized complexity and approximation algorithms '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics.
Marx, Dániel +2 more
core +1 more source
The Parameterized Complexity of Positional Games [PDF]
CoRR, 2017 To appear in the Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Bonnet, Edouard +4 more
openaire +5 more sources