Fixed-parameter tractability and completeness II: On completeness for W[1]
From MaRDI portal
Publication:673779
Recommendations
Cites work
- 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
- 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?)
- Nondeterminism within $P^ * $
- On the parameterized complexity of short computation and factorization
Cited in
(only showing first 100 items - show all)- On the parameterized complexity of multiple-interval graph problems
- A heuristic approach for the max-min diversity problem based on max-clique
- Parameterized complexity of finding regular induced subgraphs
- Before and after vacuity
- Parameterized circuit complexity and the \(W\) hierarchy
- Threshold dominating sets and an improved characterization of \(W[2]\)
- Approximation algorithms for knapsack problems with cardinality constraints
- The hardness of perfect phylogeny, feasible register assignment and other problems on thin colored graphs
- Perfect Code is \(W[1]\)-complete
- Enhancing quantum annealing performance for the molecular similarity problem
- Approximation for vertex cover in -conflict graphs
- Change-making problems revisited: a parameterized point of view
- Path-contractions, edge deletions and connectivity preservation
- Turbocharging treewidth heuristics
- Maximum disjoint paths on edge-colored graphs: approximability and tractability
- Finding a potential community in networks
- Computing the number of induced copies of a fixed graph in a bounded degree graph
- Improved approximation algorithms for capacitated fault-tolerant \(k\)-center
- Two decomposition algorithms for solving a minimum weight maximum clique model for the air conflict resolution problem
- On the complexity of finding and counting solution-free sets of integers
- Parameterized computational complexity of finding small-diameter subgraphs
- Multivariate complexity analysis of Swap Bribery
- Cliques with maximum/minimum edge neighborhood and neighborhood density
- Parameterized complexity of vertex colouring
- Parameterized complexity of finding subgraphs with hereditary properties.
- Preprocessing of intractable problems
- Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
- The Turing way to parameterized complexity
- The \(k\)-feature set problem is \(W[2]\)-complete
- Solving large FPT problems on coarse-grained parallel machines
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
- \(W[2]\)-hardness of precedence constrained \(K\)-processor scheduling
- The complexity of irredundant sets parameterized by size
- Partial information network queries
- Hardness and tractability of the \(\gamma\)-complete subgraph problem
- On the induced matching problem in Hamiltonian bipartite graphs
- The complexity of dependency detection and discovery in relational databases
- Parameterized algorithms and complexity for the traveling purchaser problem and its variants
- On the complexity of approximately matching a string to a directed graph
- Few induced disjoint paths for \(H\)-free graphs
- Length-bounded cuts: proper interval graphs and structural parameters
- Envy-free allocations respecting social networks
- Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes
- From the \(W\)-hierarchy to XNLP. Classes of fixed parameter intractability
- On the -interval and the -convexity numbers of graphs and graph products
- Checking regular invariance under tightly-controlled string modifications
- Reoptimization of parameterized problems
- Parameterized complexity of conflict-free matchings and paths
- Parameterized complexity of independent set reconfiguration problems
- Assigning times to minimise reachability in temporal graphs
- The envy-free matching problem with pairwise preferences
- Detecting fixed patterns in chordal graphs in polynomial time
- Applying modular decomposition to parameterized cluster editing problems
- CP decomposition and weighted clique problem
- Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers
- An improved linear kernel for complementary maximal strip recovery: simpler and smaller
- The complexity of finding harmless individuals in social networks
- On the space and circuit complexity of parameterized problems: classes and completeness
- Finding disjoint paths in networks with star shared risk link groups
- An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
- Tennis manipulation: can we help Serena Williams win another tournament? Or can we control a knockout tournament with reasonable complexity?
- A fixed-parameter tractable algorithm for matrix domination
- Parameterized complexity classes beyond para-NP
- A multivariate framework for weighted FPT algorithms
- Improved parameterized algorithms for network query problems
- Knapsack problems: a parameterized point of view
- Distance-\(d\) independent set problems for bipartite and chordal graphs
- Exact algorithms for problems related to the densest \(k\)-set problem
- Algorithms in the W-hierarchy
- Open problems around exact algorithms
- On the structure of parameterized problems in NP
- On the kernelization of split graph problems
- Kernelization and approximation of distance-r independent sets on nowhere dense graphs
- Optimizing reachability sets in temporal graphs by delaying
- Tight FPT approximation for constrained k-center and k-supplier
- Components in time-varying graphs
- On the independent set problem in random graphs
- Parameterized complexity in multiple-interval graphs: domination
- On the efficiency of polynomial time approximation schemes
- The birth and early years of parameterized complexity
- The Impact of Parameterized Complexity to Interdisciplinary Problem Solving
- A basic parameterized complexity primer
- FPT Suspects and Tough Customers: Open Problems of Downey and Fellows
- An improved fixed-parameter algorithm for vertex cover
- Complexity and kernels for bipartition into degree-bounded induced graphs
- Improved parameterized algorithms for network query problems
- Maximum minimal vertex cover parameterized by vertex cover
- On the 2-club polytope of graphs
- Fixed-parameter decidability: extending parameterized complexity analysis
- Parameterized complexity of \(k\)-anonymity: hardness and tractability
- Improved approximations for hard optimization problems via problem instance classification
- Kernelization of edge perfect code and its variants
- Parameterized Complexity Classes under Logical Reductions
- Evaluation and enumeration problems for regular path queries
- The Parameterized Complexity of Maximality and Minimality Problems
- A Purely Democratic Characterization of W[1]
- Parameterized complexity of \(k\)-anonymity: hardness and tractability
- Kernelization: new upper and lower bound techniques
- The density maximization problem in graphs
- On testing monomials in multivariate polynomials
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)
