Parametrized complexity theory.
From MaRDI portal
Publication:2488567
Research exposition (monographs, survey articles) pertaining to computer science (68-02) Analysis of algorithms and problem complexity (68Q25) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Model theory of finite structures (03C13) Automata and formal grammars in connection with logical questions (03D05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19) Complexity of computation (including implicit computational complexity) (03D15)
Recommendations
Cited in
(only showing first 100 items - show all)- Computing hitting set kernels by \(\mathrm{AC}^0\)-circuits
- Two-layer planarization parameterized by feedback edge set
- The complexity of the stamp folding problem
- Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
- Deciding the winner in \(k\) rounds for DISJOINT ARROWS, a new combinatorial partizan game
- Maximum balanced subgraph problem parameterized above lower bound
- Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
- Parameterized maximum path coloring
- A new bound for 3-satisfiable MaxSat and its algorithmic application
- Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization
- Revisiting the complexity of and/or graph solution
- Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking
- Parameterized complexity of connected even/odd subgraph problems
- Parametrised complexity of satisfiability in temporal logic
- A note on the gap between rank and border rank
- Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
- Parameterized complexity results for a model of theory of mind based on dynamic epistemic logic
- Partially polynomial kernels for set cover and test cover
- Counting Answers to Existential Questions
- Augmenting tractable fragments of abstract argumentation
- Searching the \(k\)-change neighborhood for TSP is W[1]-hard
- Directed NLC-width
- Parameterized complexity of conflict-free matchings and paths
- Constrained synchronization and commutativity
- Enumerating models of DNF faster: breaking the dependency on the formula size
- Decomposing Quantified Conjunctive (or Disjunctive) Formulas
- Counting edge-injective homomorphisms and matchings on restricted graph classes
- A multistage view on 2-satisfiability
- The parameterized complexity of the minimum shared edges problem
- scientific article; zbMATH DE number 7278041 (Why is no real title available?)
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- Packing arc-disjoint cycles in oriented graphs
- Parameterised and fine-grained subgraph counting, modulo 2
- Dynamic kernels for hitting sets and set packing
- Discrete multi-module capacitated lot-sizing problems with multiple items
- How bad is the freedom to Flood-It?
- Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs
- The multicolored graph realization problem
- Practical access to dynamic programming on tree decompositions
- Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
- Algorithms Solving the Matching Cut Problem
- On treewidth and stable marriage: parameterized algorithms and hardness results (complete characterization)
- Randomised enumeration of small witnesses using a decision oracle
- Bandwidth on AT-free graphs
- Backdoors to q-Horn
- Parameterizations of test cover with bounded test sizes
- A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem
- Parameterized algorithms for finding square roots
- A probabilistic approach to problems parameterized above or below tight bounds
- Parameterized and subexponential-time complexity of satisfiability problems and applications
- Complexity and monotonicity results for domination games
- On the parameterized complexity of associative and commutative unification
- Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review
- Towards fixed-parameter tractable algorithms for abstract argumentation
- Note on Max Lin-2 above average
- Kernelization: new upper and lower bound techniques
- Optimal-size problem kernels for d-Hitting Set in linear time and space
- scientific article; zbMATH DE number 7559376 (Why is no real title available?)
- The parameterized complexity of finding point sets with hereditary properties
- The parameterized complexity of the rainbow subgraph problem
- The complexity of quantum circuit mapping with fixed parameters
- Deciding Parity Games in Quasi-polynomial Time
- On the universal steganography of optimal rate
- Approximation schemes for the generalized extensible bin packing problem
- A Retrospective on (Meta) Kernelization
- scientific article; zbMATH DE number 7232976 (Why is no real title available?)
- On the parameterized complexity of associative and commutative unification
- The effect of homogeneity on the computational complexity of combinatorial data anonymization
- On compiling structured CNFs to OBDDs
- Parameterized domination in circle graphs
- Discrete metric spaces: structure, enumeration, and 0-1 laws
- Kernelization complexity of possible winner and coalitional manipulation problems in voting
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- scientific article; zbMATH DE number 7561480 (Why is no real title available?)
- A Linear Kernel for Planar Feedback Vertex Set
- Exact and Fixed Parameter Tractable Algorithms for Max-Conflict-Free Coloring in Hypergraphs
- On the complexity of coloring ‐graphs
- Counting induced subgraphs: a topological approach to \#W[1]-hardness
- A multivariate complexity analysis of the material consumption scheduling problem
- Detecting fixed patterns in chordal graphs in polynomial time
- A dichotomy result for Ramsey quantifiers
- Approximation algorithms for orienting mixed graphs
- Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle
- Explicit small heights in infinite non-abelian extensions
- A more effective linear kernelization for cluster editing
- Parameterized computational complexity of Dodgson and Young elections
- Solving hard stable matching problems involving groups of similar agents
- Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension
- Exact combinatorial algorithms and experiments for finding maximum \(k\)-plexes
- Designing FPT algorithms for cut problems using randomized contractions
- Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes
- Aspects of a multivariate complexity analysis for rectangle tiling
- Multi-attribute proportional representation
- Improved bounds for spanning trees with many leaves
- Scheduling with cardinality dependent unavailability periods
- FPT algorithms for path-transversal and cycle-transversal problems
- Fast learning of relational dependency networks
- Tennis manipulation: can we help Serena Williams win another tournament? Or can we control a knockout tournament with reasonable complexity?
- Bounding the running time of algorithms for scheduling and packing problems
- Finer tight bounds for coloring on clique-width
This page was built for publication: Parametrized complexity theory.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2488567)
