On miniaturized problems in parameterized complexity theory
From MaRDI portal
Publication:820145
DOI10.1016/J.TCS.2005.10.003zbMATH Open1087.68034OpenAlexW2165019867MaRDI QIDQ820145FDOQ820145
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)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Which problems have strongly exponential complexity?
- On the complexity of \(k\)-SAT
- Vertex packings: Structural properties and algorithms
- Cutting up is hard to do: the parameterised complexity of \(k\)-cut and related problems
- Linear FPT reductions and computational lower bounds
- Algorithms and Data Structures
- Fixed-parameter tractability, definability, and model-checking
- Automata, Languages and Programming
Cited In (31)
- Compactors for parameterized counting problems
- Parameterized Complexity and Subexponential-Time Computability
- Fine-grained parameterized complexity analysis of graph coloring problems
- Pursuing a fast robber on a graph
- On the algorithmic effectiveness of digraph decompositions and complexity measures
- VC bounds on the cardinality of nearly orthogonal function classes
- On families of categorial grammars of bounded value, their learnability and related complexity questions
- On the upward book thickness problem: combinatorial and complexity results
- Covering graphs with few complete bipartite subgraphs
- Containment relations in split graphs
- Spined categories: generalizing tree-width beyond graphs
- Book review of: Rolf Niedermeier, Invitation to fixed-parameter algorithms
- Stable assignment with couples: parameterized complexity and local search
- Paths of bounded length and their cuts: parameterized complexity and algorithms
- Parameterized and Subexponential-Time Complexity of Satisfiability Problems and Applications
- Confronting intractability via parameters
- Minimization problems for parity OBDDs
- Complexity of manipulation and bribery in judgment aggregation for uniform premise-based quota rules
- Parameterized and subexponential-time complexity of satisfiability problems and applications
- Fixed-parameter decidability: Extending parameterized complexity analysis
- Parameterized analysis and crossing minimization problems
- Integer programming in parameterized complexity: five miniatures
- An annotated bibliography on 1-planarity
- Parameterized and Exact Computation
- Color spanning objects: algorithms and hardness results
- Practical complexities of probabilistic algorithms for solving Boolean polynomial systems
- Parameterized algorithms for module map problems
- Complexity of independency and cliquy trees
- The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT
- Domination and convexity problems in the target set selection model
- Faster and enhanced inclusion-minimal cograph completion
This page was built for publication: On miniaturized problems in parameterized complexity theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q820145)
