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)- The Turing way to parameterized complexity
- Parameterized complexity of team formation in social networks
- Some results on more flexible versions of Graph Motif
- Huge tables and multicommodity flows are fixed-parameter tractable via unimodular integer Carathéodory
- Parameterized complexity of team formation in social networks
- Subset feedback vertex set on graphs of bounded independent set size
- Computing nearest neighbour interchange distances between ranked phylogenetic trees
- Parameterized algorithms for the module motif problem
- The parameterised complexity of list problems on graphs of bounded treewidth
- Fly-automata for checking \(\mathrm{MSO}_2\) graph properties
- A new approach for contact graph representations and its applications
- Knapsack problems: a parameterized point of view
- Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
- An FPT-algorithm for modifying a graph of bounded treewidth to decrease the size of its dominating set using minimum modification
- New limits to classical and quantum instance compression
- Parameterized approximation algorithms for packing problems
- Computations by fly-automata beyond monadic second-order logic
- Kernels for packing and covering problems
- A refined complexity analysis of degree anonymization in graphs
- The mixed Chinese postman problem parameterized by pathwidth and treedepth
- Subset feedback vertex set on graphs of bounded independent set size
- Graph editing to a given degree sequence
- Courcelle's theorem for triangulations
- Do branch lengths help to locate a tree in a phylogenetic network?
- Computation Models for Parameterized Complexity
- Graph editing to a given degree sequence
- Backdoors into heterogeneous classes of SAT and CSP
- Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees
- On the complexity landscape of the domination chain
- Identification, location-domination and metric dimension on interval and permutation graphs. II: Algorithms and complexity
- scientific article; zbMATH DE number 2234775 (Why is no real title available?)
- Path-driven orientation of mixed graphs
- scientific article; zbMATH DE number 7651188 (Why is no real title available?)
- Algorithms and complexity for metric dimension and location-domination on interval and permutation graphs
- Recognizing \(k\)-equistable graphs in FPT time
- Parameterized algorithms
- Finding large degree-anonymous subgraphs is hard
- Parameterized tractability of the maximum-duo preservation string mapping problem
- Reduction rules for the maximum parsimony distance on phylogenetic trees
- On the complexity of connection games
- Polynomial kernels and user reductions for the workflow satisfiability problem
- Solving linear equations parameterized by Hamming weight
- A guide to algorithm design. Paradigms, methods, and complexity analysis
- Rural postman parameterized by the number of components of required edges
- Kernelization of edge perfect code and its variants
- FPT algorithms for domination in sparse graphs and beyond
- Parametrized complexity theory.
- An algorithm for finding approximate Nash equilibria in bimatrix games
- On the hardness of maximum rank aggregation problems
- Subexponential parameterized algorithms and kernelization on almost chordal graphs
- Algorithms for the workflow satisfiability problem engineered for counting constraints
- New analysis and computational study for the planar connected dominating set problem
- \(\mathrm{H}\)-index manipulation by merging articles: models, theory, and experiments
- Metric dimension of bounded width graphs
- Editing to a connected graph of given degrees
- Parameterized complexity of the anchored \(k\)-core problem for directed graphs
- Parameterizations of test cover with bounded test sizes
- Parameterized complexity of the \(k\)-arc Chinese postman problem
- On the parameterized complexity of b-\textsc{chromatic number}
- Parameterized algorithms for finding square roots
- Linear-vertex kernel for the problem of packing \(r\)-stars into a graph without long induced paths
- Complexity and monotonicity results for domination games
- On critical node problems with vulnerable vertices
- Structural parameterizations of the mixed Chinese postman problem
- scientific article; zbMATH DE number 7053262 (Why is no real title available?)
- Deterministic algorithms for matching and packing problems based on representative sets
- Win-win kernelization for degree sequence completion problems
- Prices matter for the parameterized complexity of shift bribery
- Chordal editing is fixed-parameter tractable
- Pattern backtracking algorithm for the workflow satisfiability problem with user-independent constraints
- Combinatorial voter control in elections
- On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results
- A polynomial kernel for bipartite permutation vertex deletion
- Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size
- Twin-width and polynomial kernels
- Parameterized complexity of voter control in multi-peaked elections
- The complexity of finding temporal separators under waiting time constraints
- The parameterized hardness of the \(k\)-center problem in transportation networks
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Metric dimension parameterized by treewidth
- Finding Temporal Paths Under Waiting Time Constraints.
- Parameterized (approximate) defective coloring
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- On the complexity of the smallest grammar problem over fixed alphabets
- Reducing graph transversals via edge contractions
- On the parameterized complexity of contraction to generalization of trees
- Parameterized complexity of multi-node hubs
- On the complexity of approximately matching a string to a directed graph
- MUL-tree pruning for consistency and optimal reconciliation -- complexity and algorithms
- Enumeration and maximum number of maximal irredundant sets for chordal graphs
- Efficiently enumerating hitting sets of hypergraphs arising in data profiling
- A relaxation of the directed disjoint paths problem: a global congestion metric helps
- Mim-width. I. Induced path problems
- Single-machine scheduling with release times, deadlines, setup times, and rejection
- On structural parameterizations of the edge disjoint paths problem
- Solving partition problems almost always requires pushing many vertices around
- A tight lower bound for vertex planarization on graphs of bounded treewidth
- Parameterized (approximate) defective coloring
- Improved kernel and algorithm for claw and diamond free edge deletion based on refined observations
- The power of cut-based parameters for computing edge-disjoint paths
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)
