Parameterized complexity
From MaRDI portal
The book contains Downey and Fellows' argument against the claim that computational complexity is a mathematical pedantry, by and large irrelevant to modern science. They introduce a new way to look at difficult problems (NP-complete, in the jargon) which allows them to prove (surprisingly) that some of these problems admit good algorithms for data sets of any size provided that some parameter is small enough. This is how parameterized complexity enters the game: it has generated a very good book and an interesting subject. Does it support the claim that ``computational complexity is serving the community?
Recommendations
Cited in
(only showing first 100 items - show all)- A bounded search tree algorithm for parameterized face cover
- A fixed parameter algorithm for optimal convex partitions
- On k-connectivity problems with sharpened triangle inequality
- Fixed-parameter algorithms for protein similarity search under mRNA structure constraints
- Parameterized algorithmics for linear arrangement problems
- Efficiency in exponential time for domination-type problems
- Some tractable instances of interval data minmax regret problems
- Closest 4-leaf power is fixed-parameter tractable
- Parameterizing above or below guaranteed values
- The minimum spanning strong subdigraph problem is fixed parameter tractable
- Treewidth and logical definability of graph products
- The complexity of the matroid-greedoid partition problem
- Computing small partial coverings
- Finding occurrences of protein complexes in protein-protein interaction graphs
- Red-blue covering problems and the consecutive ones property
- A 3-approximation algorithm for the subtree distance between phylogenies
- On parameterized complexity of the multi-MCS problem
- Covering graphs with few complete bipartite subgraphs
- Stacks in canonical RNA pseudoknot structures
- A simple algorithm for multicuts in planar graphs with outer terminals
- Parameterized complexity of finding regular induced subgraphs
- Algorithms for optimal outlier removal
- Linear CNF formulas and satisfiability
- The parameterized complexity of the induced matching problem
- On parameterized exponential time complexity
- Parameterized computational complexity of control problems in voting systems
- On problems without polynomial kernels
- Parameterized learnability of juntas
- Fixed-parameter algorithms for Kemeny rankings
- Isolation concepts for clique enumeration: comparison and computational experiments
- Parameterized complexity of candidate control in elections and related digraph problems
- Computational study on planar dominating set problem
- A faster parameterized algorithm for set packing
- On the shape of decomposable trees
- The union of minimal hitting sets: parameterized combinatorial bounds and counting
- Algorithms for generating convex sets in acyclic digraphs
- Threshold dominating cliques in random graphs and interval routing
- Bandwidth of bipartite permutation graphs in polynomial time
- A fixed-parameter tractability result for multicommodity demand flow in trees
- Fixed-parameter tractability of graph modification problems for hereditary properties
- On the complexity of finding common approximate substrings.
- Default reasoning from conditional knowledge bases: Complexity and tractable cases
- An improved algorithm for the jump number problem
- Perfect Code is \(W[1]\)-complete
- The computational complexity of densest region detection
- A general method to speed up fixed-parameter-tractable algorithms
- Solving multi-granularity temporal constraint networks
- A (3+)k-vertex kernel for edge-disjoint triangle packing
- Triangle-free planar graphs with small independence number
- Forming \(k\) coalitions and facilitating relationships in social networks
- Two edge modification problems without polynomial kernels
- The complexity of probabilistic lobbying
- Critical and maximum independent sets of a graph
- A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees
- Note on maximal bisection above tight lower bound
- The \(k\)-leaf spanning tree problem admits a klam value of 39
- Multivariate complexity analysis of geometric \textsc{Red Blue Set Cover}
- Chain minors are FPT
- Change-making problems revisited: a parameterized point of view
- On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability
- Exact and superpolynomial approximation algorithms for the \textsc{densest \textit{K}-subgraph} problem
- Parameterized approximation via fidelity preserving transformations
- On the parameterized complexity of \((k,s)\)-SAT
- Multi-attribute proportional representation
- A new decomposition technique for maximal clique enumeration for sparse graphs
- The complexity of routing with collision avoidance
- Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms
- The critical node detection problem in networks: a survey
- Min-max cover of a graph with a small number of parts
- Polynomial kernels for deletion to classes of acyclic digraphs
- Complexity of minimum irreducible infeasible subsystem covers for flow networks
- FPT-algorithms for some problems related to integer programming
- Augmenting tractable fragments of abstract argumentation
- Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs
- Embeddings of \(k\)-connected graphs of pathwidth \(k\)
- Balanced vertex-orderings of graphs
- Core instances for testing: a case study
- Polynomial and APX-hard cases of the individual haplotyping problem
- Contraction and deletion blockers for perfect graphs and \(H\)-free graphs
- Preprocessing of intractable problems
- On the parametric complexity of schedules to minimize tardy tasks.
- Describing parameterized complexity classes
- The Turing way to parameterized complexity
- The \(k\)-feature set problem is \(W[2]\)-complete
- Solving large FPT problems on coarse-grained parallel machines
- Call control with \(k\) rejections
- On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
- Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms
- Hard problems in similarity searching
- The complexity of first-order and monadic second-order logic revisited
- Decidability of bounded second order unification
- A new view on rural postman based on Eulerian extension and matching
- Improved Steiner tree algorithms for bounded treewidth
- A golden ratio parameterized algorithm for cluster editing
- Even faster parameterized cluster deletion and cluster editing
- Subexponential algorithms for partial cover problems
- Automata for the verification of monadic second-order graph properties
- Towards optimal kernel for connected vertex cover in planar graphs
- Fixed-parameter evolutionary algorithms and the vertex cover problem
- The parameterized complexity of some minimum label problems
This page was built for publication: Parameterized complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4393480)
