Fundamentals of parameterized complexity
From MaRDI portal
Research exposition (monographs, survey articles) pertaining to computer science (68-02) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) General topics in the theory of algorithms (68W01)
Recommendations
- Parameterized complexity: the main ideas and connections to practical computing
- scientific article; zbMATH DE number 1956210
- A basic parameterized complexity primer
- scientific article; zbMATH DE number 1161563
- scientific article; zbMATH DE number 2080999
- A parameterized complexity tutorial
- Computation Models for Parameterized Complexity
- Polynomial time approximation schemes and parameterized complexity
- Mathematical Foundations of Computer Science 2004
Cited in
(only showing first 100 items - show all)- Structural parameterization for minimum conflict-free colouring
- Multivariate algorithmics for finding cohesive subnetworks
- Parameterized complexity results for a model of theory of mind based on dynamic epistemic logic
- Polynomial kernels for hitting forbidden minors under structural parameterizations
- Counting Answers to Existential Questions
- A parameterized complexity view on collapsing \(k\)-cores
- Compactors for parameterized counting problems
- Directed NLC-width
- Tight lower bounds for the workflow satisfiability problem based on the strong exponential time hypothesis
- Parameterized complexity of conflict-free matchings and paths
- On the bond polytope
- Revisiting the parameterized complexity of maximum-duo preservation string mapping
- Lossy kernelization of same-size clustering
- Parameterised algorithms for deletion to classes of DAGs
- The parameterized complexity of the minimum shared edges problem
- scientific article; zbMATH DE number 7278041 (Why is no real title available?)
- Parameterized algorithms for multi-label periodic temporal graph realization
- Efficient diagonalization of symmetric matrices associated with graphs of small treewidth
- Synthesis of Pure and Impure Petri Nets with Restricted Place-environments: Complexity Issues
- Packing arc-disjoint cycles in oriented graphs
- Parameterised and fine-grained subgraph counting, modulo 2
- Dynamic kernels for hitting sets and set packing
- Consensus patterns (probably) has no EPTAS
- A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps.
- On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic
- Being an influencer is hard: the complexity of influence maximization in temporal graphs with a fixed source
- FPT approximation using treewidth: capacitated vertex cover, target set selection and vector dominating set
- A parameterized halting problem, _0 truth and the MRDP theorem
- Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
- Algorithms Solving the Matching Cut Problem
- Parameterized complexity of voter control in multi-peaked elections
- On treewidth and stable marriage: parameterized algorithms and hardness results (complete characterization)
- Structural parameterizations of budgeted graph coloring
- Backdoors for linear temporal logic
- Randomised enumeration of small witnesses using a decision oracle
- scientific article; zbMATH DE number 7559442 (Why is no real title available?)
- Parameterized complexity of the anchored k-core problem for directed graphs
- Parameterizations of test cover with bounded test sizes
- Parameterized algorithms for finding square roots
- Linear-vertex kernel for the problem of packing r-stars into a graph without long induced paths
- Parameterized and subexponential-time complexity of satisfiability problems and applications
- Complexity and monotonicity results for domination games
- Combining SAT solvers with computer algebra systems to verify combinatorial conjectures
- Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review
- Jumping finite automata: characterizations and complexity
- Hitting minors on bounded treewidth graphs. I: General upper bounds
- Collaborating with Hans: Some Remaining Wonderments
- scientific article; zbMATH DE number 7559376 (Why is no real title available?)
- On the complexity of solution extension of optimization problems
- On the maximum colorful arborescence problem and color hierarchy graph structure
- The parameterized complexity of the rainbow subgraph problem
- Deciding Parity Games in Quasi-polynomial Time
- \(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms
- Fixed-parameter algorithms for Vertex Cover \(P_3\)
- On unrooted and root-uncertain variants of several well-known phylogenetic network problems
- Generalized pseudoforest deletion: algorithms and uniform kernel
- Quick but odd growth of cacti
- A fixed-parameter algorithm for scheduling unit dependent tasks on parallel machines with time windows
- Parameterized approximation algorithms for packing problems
- Multistage graph problems on a global budget
- Breakpoint distance and PQ-trees
- Acyclic coloring parameterized by directed clique-width
- Parameterized complexity of d-hitting set with quotas
- Sorting by multi-cut rearrangements
- Fast exact algorithms using Hadamard product of polynomials
- A Retrospective on (Meta) Kernelization
- On computing the Hamiltonian index of graphs
- On computing large temporal (unilateral) connected components
- Preventing small \(\mathbf{(s,t)} \)-cuts by protecting edges
- On compiling structured CNFs to OBDDs
- scientific article; zbMATH DE number 6970796 (Why is no real title available?)
- Complexity of control by partitioning veto elections and of control by adding candidates to plurality elections
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- scientific article; zbMATH DE number 7651188 (Why is no real title available?)
- Fine-grained parameterized complexity analysis of graph coloring problems
- Minimizing machine assignment costs over \(\Delta\)-approximate solutions of the scheduling problem \(P||C_{\max}\)
- Possibilistic keys
- Parameterized resiliency problems
- Hardness results of global total \(k\)-domination problem in graphs
- Packing cycles faster than Erdős-Pósa
- On the complexity of coloring ‐graphs
- Grundy Coloring and friends, half-graphs, bicliques
- scientific article; zbMATH DE number 7559375 (Why is no real title available?)
- A multivariate complexity analysis of the material consumption scheduling problem
- Bribery and control in stable marriage
- Solving hard stable matching problems involving groups of similar agents
- Fine-grained complexity of safety verification
- An algorithm for finding approximate Nash equilibria in bimatrix games
- Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes
- A measure and conquer approach for the parameterized bounded degree-one vertex deletion
- Structural parameterization of minus domination
- On critical node problems with vulnerable vertices
- Designing FPT algorithms for cut problems using randomized contractions
- Scheduling with cardinality dependent unavailability periods
- \(\mathcal{P}\)-matchings parameterized by treewidth
- Path-driven orientation of mixed graphs
- Parameterized complexity of the workflow satisfiability problem
- Vertex cover and feedback vertex set above and below structural guarantees
- Twin-width. VIII: Delineation and win-wins
- On the complexity of problems on tree-structured graphs
This page was built for publication: Fundamentals of parameterized complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q383833)
