On miniaturized problems in parameterized complexity theory
From MaRDI portal
Publication:820145
DOI10.1016/j.tcs.2005.10.003zbMath1087.68034OpenAlexW2165019867MaRDI QIDQ820145
Publication date: 6 April 2006
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2005.10.003
Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Compactors for parameterized counting problems, Parameterized Complexity and Subexponential-Time Computability, Parameterized analysis and crossing minimization problems, An annotated bibliography on 1-planarity, Parameterized and Subexponential-Time Complexity of Satisfiability Problems and Applications, Color spanning objects: algorithms and hardness results, Spined categories: generalizing tree-width beyond graphs, Parameterized and subexponential-time complexity of satisfiability problems and applications, Fixed-parameter decidability: Extending parameterized complexity analysis, Complexity of manipulation and bribery in judgment aggregation for uniform premise-based quota rules, VC bounds on the cardinality of nearly orthogonal function classes, Domination and convexity problems in the target set selection model, Stable assignment with couples: parameterized complexity and local search, Paths of bounded length and their cuts: parameterized complexity and algorithms, On the algorithmic effectiveness of digraph decompositions and complexity measures, The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT, Book review of: Rolf Niedermeier, Invitation to fixed-parameter algorithms, Confronting intractability via parameters, Pursuing a fast robber on a graph, On families of categorial grammars of bounded value, their learnability and related complexity questions, Faster and enhanced inclusion-minimal cograph completion, Parameterized algorithms for module map problems, Complexity of independency and cliquy trees, On the upward book thickness problem: combinatorial and complexity results, Covering graphs with few complete bipartite subgraphs, Practical complexities of probabilistic algorithms for solving Boolean polynomial systems, Containment relations in split graphs, Fine-grained parameterized complexity analysis of graph coloring problems
Cites Work
- Which problems have strongly exponential complexity?
- Fixed-Parameter Tractability, Definability, and Model-Checking
- Linear FPT reductions and computational lower bounds
- Vertex packings: Structural properties and algorithms
- Automata, Languages and Programming
- Algorithms and Data Structures
- On the complexity of \(k\)-SAT
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
