Fixed-parameter tractability and completeness II: On completeness for W[1]
From MaRDI portal
Publication:673779
Recommendations
Cites work
- scientific article; zbMATH DE number 125608 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 512804 (Why is no real title available?)
- scientific article; zbMATH DE number 512844 (Why is no real title available?)
- scientific article; zbMATH DE number 1142299 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 1499087 (Why is no real title available?)
- scientific article; zbMATH DE number 219251 (Why is no real title available?)
- scientific article; zbMATH DE number 806748 (Why is no real title available?)
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
- Graph minors. XIII: The disjoint paths problem
- Graph minors. XX: Wagner's conjecture
- Nondeterminism within $P^ * $
- On the parameterized complexity of short computation and factorization
Cited in
(only showing first 100 items - show all)- Confronting intractability via parameters
- Complexity and kernels for bipartition into degree-bounded induced graphs
- On the \(\Delta \)-interval and the \(\Delta \)-convexity numbers of graphs and graph products
- Checking regular invariance under tightly-controlled string modifications
- Knapsack problems: a parameterized point of view
- Fast local search methods for solving limited memory influence diagrams
- On the hardness of labeled correlation clustering problem: a parameterized complexity view
- Sublinear separators, fragility and subexponential expansion
- Approximation algorithms for knapsack problems with cardinality constraints
- Maximum minimal vertex cover parameterized by vertex cover
- On inclusionwise maximal and maximum cardinality \(k\)-clubs in graphs
- Improving the non‐compensatory trace‐clustering decision process
- Parameterized Complexity for Domination Problems on Degenerate Graphs
- An improved linear kernel for complementary maximal strip recovery: simpler and smaller
- Parameterized complexity of vertex colouring
- Counting vanishing matrix-vector products
- Efficient algorithms for counting parameterized list H-colorings
- A heuristic approach for the max-min diversity problem based on max-clique
- Bounded Tree-Width and CSP-Related Problems
- Approximation for vertex cover in -conflict graphs
- Change-making problems revisited: a parameterized point of view
- Assigning times to minimise reachability in temporal graphs
- An algorithmic framework for locally constrained homomorphisms
- Perfect Code is \(W[1]\)-complete
- The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
- On the structure of parameterized problems in NP
- Treewidth versus clique number. I: Graph classes with a forbidden structure
- Correcting gene tree by removal and modification: tractability and approximability
- There is no EPTAS for two-dimensional knapsack
- Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack
- Enhancing quantum annealing performance for the molecular similarity problem
- Parameterized complexity of \(k\)-anonymity: hardness and tractability
- Multivariate complexity analysis of Swap Bribery
- Chordless paths through three vertices
- Length-bounded cuts: proper interval graphs and structural parameters
- On notions of regularity for data languages
- scientific article; zbMATH DE number 7561704 (Why is no real title available?)
- Controlling entity integrity with key sets
- Subgraph isomorphism on graph classes that exclude a substructure
- The challenges of unbounded treewidth in parameterised subgraph counting problems
- The Turing way to parameterized complexity
- Preprocessing of intractable problems
- Parameterized complexity classes beyond para-NP
- Balanced stable marriage: how close is close enough?
- Exact weight subgraphs and the \(k\)-sum conjecture
- Parameterized Counting and Cayley Graph Expanders
- Approximation schemes for deal splitting and covering integer programs with multiplicity constraints
- Partial information network queries
- Optimizing reachability sets in temporal graphs by delaying
- Causal graphs and structurally restricted planning
- The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
- An analysis of the W*-hierarchy
- The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side
- Reoptimization of parameterized problems
- Improved parameterized algorithms for network query problems
- An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
- Parameterized algorithms and complexity for the traveling purchaser problem and its variants
- scientific article; zbMATH DE number 512844 (Why is no real title available?)
- The complexity ecology of parameters: An illustration using bounded max leaf number
- Tight FPT approximation for constrained \(k\)-center and \(k\)-supplier
- CP decomposition and weighted clique problem
- On the induced matching problem in Hamiltonian bipartite graphs
- Exact algorithms for problems related to the densest \(k\)-set problem
- Exact and heuristic methods for a workload allocation problem with chain precedence constraints
- Maximum minimal vertex cover parameterized by vertex cover
- Algorithms in the W-hierarchy
- On the complexity of approximately matching a string to a directed graph
- A fixed-parameter tractable algorithm for matrix domination
- Path-contractions, edge deletions and connectivity preservation
- The density maximization problem in graphs
- A multivariate framework for weighted FPT algorithms
- The complexity of irredundant sets parameterized by size
- FPT Suspects and Tough Customers: Open Problems of Downey and Fellows
- On the parameterized intractability of determinant maximization
- Open packing in \(H\)-free graphs and subclasses of split graphs
- \(W[2]\)-hardness of precedence constrained \(K\)-processor scheduling
- Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems
- scientific article; zbMATH DE number 7764095 (Why is no real title available?)
- On testing monomials in multivariate polynomials
- The l-diversity problem: tractability and approximability
- Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
- Compactors for parameterized counting problems
- Parameterized complexity of \(k\)-anonymity: hardness and tractability
- Parameterized complexity of conflict-free matchings and paths
- Few induced disjoint paths for \(H\)-free graphs
- Domino treewidth
- Parameterized complexity of coloring problems: treewidth versus vertex cover
- The multicolored graph realization problem
- Parameterized algorithms for the happy set problem
- Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy
- Turbocharging treewidth heuristics
- Improved approximation algorithms for capacitated fault-tolerant \(k\)-center
- Kernelization: new upper and lower bound techniques
- The Parameterized Complexity of Maximality and Minimality Problems
- scientific article; zbMATH DE number 125608 (Why is no real title available?)
- A Retrospective on (Meta) Kernelization
- On computing large temporal (unilateral) connected components
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Detecting fixed patterns in chordal graphs in polynomial time
- Exact algorithms for restricted subset feedback vertex set in chordal and split graphs
This page was built for publication: Fixed-parameter tractability and completeness II: On completeness for W[1]
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q673779)
