Fundamentals of parameterized complexity
From MaRDI portal
Research exposition (monographs, survey articles) pertaining to computer science (68-02) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) 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)- FO model checking on geometric graphs
- Scaffolding problems revisited: complexity, approximation and fixed parameter tractable algorithms, and some special cases
- Treewidth distance on phylogenetic trees
- Reconfiguration on nowhere dense graph classes
- Problems on finite automata and the exponential time hypothesis
- Homothetic polygons and beyond: maximal cliques in intersection graphs
- A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
- The \(k\)-leaf spanning tree problem admits a klam value of 39
- Kernels for deletion to classes of acyclic digraphs
- Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs
- Change-making problems revisited: a parameterized point of view
- Improved FPT algorithms for weighted independent set in bull-free graphs
- Bivariate complexity analysis of \textsc{Almost Forest Deletion}
- Structured proportional representation
- Parameterized approximation via fidelity preserving transformations
- On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results
- A connection between sports and matroids: how many teams can we beat?
- The many facets of upper domination
- Parameterized complexity of team formation in social networks
- Corrigendum to: ``Advice classes of parameterized tractability
- Parameterized algorithms for stable matching with ties and incomplete lists
- Cliques enumeration and tree-like resolution proofs
- A theory and algorithms for combinatorial reoptimization
- Solving problems on graphs of high rank-width
- Parameterized complexity of theory of mind reasoning in dynamic epistemic logic
- Complexity dichotomies for the \textsc{Minimum} \(\mathcal{F}\)-\textsc{Overlay} problem
- Inapproximability of rank, clique, Boolean, and maximum induced matching-widths under small set expansion hypothesis
- Exact algorithms for finding well-connected 2-clubs in sparse real-world graphs: theory and experiments
- Computational complexity aspects of point visibility graphs
- Backdoors for linear temporal logic
- Randomised enumeration of small witnesses using a decision oracle
- Approximate inference in Bayesian networks: parameterized complexity results
- The parameterized complexity of the rainbow subgraph problem
- Co-clustering under the maximum norm
- Multivariate algorithmics for finding cohesive subnetworks
- Track layouts, layered path decompositions, and leveled planarity
- A parameterized algorithmics framework for degree sequence completion problems in directed graphs
- Counting linear extensions: parameterizations by treewidth
- Parameterized algorithms and kernels for rainbow matching
- FPT algorithms for domination in sparse graphs and beyond
- The complexity of routing with collision avoidance
- k-distinct in- and out-branchings in digraphs
- Spy-game on graphs: complexity and simple topologies
- Algorithm to find a maximum 2-packing set in a cactus
- The complexity landscape of decompositional parameters for ILP
- Fixed-parameter algorithms for Vertex Cover \(P_3\)
- On two extensions of equimatchable graphs
- On the complexity of finding and counting solution-free sets of integers
- Fly-automata for checking \(\mathrm{MSO}_2\) graph properties
- Saving colors and max coloring: some fixed-parameter tractability results
- On unrooted and root-uncertain variants of several well-known phylogenetic network problems
- The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
- On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph
- Parameterized algorithms for conflict-free colorings of graphs
- \((k,n-k)\)-\textsc{Max-Cut}: an \(\mathcal{O}^*(2^p)\)-time algorithm and a polynomial kernel
- The Turing way to parameterized complexity
- On the parameterized complexity of contraction to generalization of trees
- The complexity of finding small separators in temporal graphs
- On the parameterized complexity of consensus clustering
- On the hardness of maximum rank aggregation problems
- Single peaked domains with tree-shaped spectra
- Single-machine scheduling with release times, deadlines, setup times, and rejection
- Hardness and tractability of the \(\gamma\)-complete subgraph problem
- On structural parameterizations of the edge disjoint paths problem
- Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
- On the complexity of the smallest grammar problem over fixed alphabets
- Subexponential parameterized algorithms and kernelization on almost chordal graphs
- Reducing graph transversals via edge contractions
- Measuring what matters: a hybrid approach to dynamic programming with treewidth
- Metric dimension parameterized by treewidth
- Hitting forbidden induced subgraphs on bounded treewidth graphs
- Efficiently enumerating hitting sets of hypergraphs arising in data profiling
- On the maximum cardinality cut problem in proper interval graphs and related graph classes
- A relaxation of the directed disjoint paths problem: a global congestion metric helps
- Optimal tree decompositions revisited: a simpler linear-time FPT algorithm
- A faster parameterized algorithm for temporal matching
- The complexity of finding temporal separators under waiting time constraints
- The complexity of dependency detection and discovery in relational databases
- Structurally parameterized \(d\)-scattered set
- Reflections on kernelizing and computing unrooted agreement forests
- The complexity of mixed-connectivity
- On the complexity of solution extension of optimization problems
- On some FPT problems without polynomial Turing compressions
- A polynomial kernel for diamond-free editing
- Improved kernel and algorithm for claw and diamond free edge deletion based on refined observations
- Refined parameterizations for computing colored cuts in edge-colored graphs
- Parameterized complexity of multi-node hubs
- On the complexity of approximately matching a string to a directed graph
- Colored cut games
- Structural parameterizations of Tracking Paths problem
- MUL-tree pruning for consistency and optimal reconciliation -- complexity and algorithms
- Revising Johnson's table for the 21st century
- A polynomial kernel for bipartite permutation vertex deletion
- Twin-width and polynomial kernels
- Introducing \textsf{lop}-kernels: a framework for kernelization lower bounds
- Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size
- Dynamic kernels for hitting sets and set packing
- Eternal vertex cover on bipartite graphs
- Lossy kernelization of same-size clustering
- Political districting to minimize cut edges
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)
