Fixed-parameter tractability and completeness II: On completeness for W[1]
From MaRDI portal
Publication:673779
DOI10.1016/0304-3975(94)00097-3zbMATH Open0873.68059OpenAlexW2061513598WikidataQ55891725 ScholiaQ55891725MaRDI QIDQ673779FDOQ673779
Authors: Michael R. Fellows, Rodney G. Downey 
Publication date: 28 February 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(94)00097-3
Recommendations
Cites Work
- Title not available (Why is that?)
- Graph minors. XX: Wagner's conjecture
- Graph minors. XIII: The disjoint paths problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Title not available (Why is that?)
- Nondeterminism within $P^ * $
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the parameterized complexity of short computation and factorization
- Title not available (Why is that?)
Cited In (only showing first 100 items - show all)
- 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
- Parameterized complexity of coloring problems: treewidth versus vertex cover
- Kernelization: new upper and lower bound techniques
- Title not available (Why is that?)
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Detecting fixed patterns in chordal graphs in polynomial time
- Refined memorization for vertex cover
- Maximum disjoint paths on edge-colored graphs: approximability and tractability
- Open problems around exact algorithms
- The \(k\)-feature set problem is \(W[2]\)-complete
- Parameterized circuit complexity and the \(W\) hierarchy
- A structural/temporal query language for business processes
- On bounded block decomposition problems for under-specified systems of equations
- Parameterized complexity of generalized domination problems
- A basic parameterized complexity primer
- Parameterized complexity of finding regular induced subgraphs
- On the complexity of fixed parameter clique and dominating set
- Parameterized computational complexity of finding small-diameter subgraphs
- The intractability of computing the Hamming distance
- On the efficiency of polynomial time approximation schemes
- Parameterized complexity of finding subgraphs with hereditary properties.
- An improved fixed-parameter algorithm for vertex cover
- Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
- Improved parameterized algorithms for network query problems
- Solving large FPT problems on coarse-grained parallel machines
- Threshold dominating sets and an improved characterization of \(W[2]\)
- Parameterized complexity of independent set reconfiguration problems
- Kernel bounds for disjoint cycles and disjoint paths
- Advice classes of parametrized tractability
- Book review of: Rolf Niedermeier, Invitation to fixed-parameter algorithms
- Before and after vacuity
- Kernelization of edge perfect code and its variants
- Finding and counting cliques and independent sets in \(r\)-uniform hypergraphs
- Applying modular decomposition to parameterized cluster editing problems
- On the parameterized complexity of multiple-interval graph problems
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
- Lower bounds on kernelization
- Complexity and kernels for bipartition into degree-bounded induced graphs
- Confronting intractability via parameters
- Knapsack problems: a parameterized point of view
- Parameterized Complexity for Domination Problems on Degenerate Graphs
- Approximation algorithms for knapsack problems with cardinality constraints
- On inclusionwise maximal and maximum cardinality \(k\)-clubs in graphs
- Parameterized complexity of vertex colouring
- 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
- Assigning times to minimise reachability in temporal graphs
- 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
- Correcting gene tree by removal and modification: tractability and approximability
- Subgraph isomorphism on graph classes that exclude a substructure
- There is no EPTAS for two-dimensional knapsack
- Multivariate complexity analysis of Swap Bribery
- Parameterized complexity of \(k\)-anonymity: hardness and tractability
- Chordless paths through three vertices
- On notions of regularity for data languages
- The Turing way to parameterized complexity
- Preprocessing of intractable problems
- Approximation schemes for deal splitting and covering integer programs with multiplicity constraints
- Optimizing reachability sets in temporal graphs by delaying
- Partial information network queries
- An analysis of the W*-hierarchy
- Causal graphs and structurally restricted planning
- Reoptimization of parameterized problems
- Title not available (Why is that?)
- Parameterized algorithms and complexity for the traveling purchaser problem and its variants
- The complexity ecology of parameters: An illustration using bounded max leaf number
- A fixed-parameter tractable algorithm for matrix domination
- Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems
- The density maximization problem in graphs
- The complexity of irredundant sets parameterized by size
- FPT Suspects and Tough Customers: Open Problems of Downey and Fellows
- \(W[2]\)-hardness of precedence constrained \(K\)-processor scheduling
- Parameterized complexity of \(k\)-anonymity: hardness and tractability
- Domino treewidth
- The multicolored graph realization problem
- Parameterized complexity of conflict-free matchings and paths
- Parameterized algorithms for the happy set problem
- Compactors for parameterized counting problems
- Few induced disjoint paths for \(H\)-free graphs
- On computing large temporal (unilateral) connected components
- Turbocharging treewidth heuristics
- A Retrospective on (Meta) Kernelization
- The Parameterized Complexity of Maximality and Minimality Problems
- Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy
- Improved approximation algorithms for capacitated fault-tolerant \(k\)-center
- Exact algorithms for restricted subset feedback vertex set in chordal and split graphs
- Parameterized complexity of finding subgraphs with hereditary properties on hereditary graph classes
- Tennis manipulation: can we help Serena Williams win another tournament? Or can we control a knockout tournament with reasonable complexity?
- On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs
- A characterization of trees having a minimum vertex cover which is also a minimum total dominating set
- On the independent set problem in random graphs
- Counting vanishing matrix-vector products
- Finding a potential community in networks
- Computing the number of induced copies of a fixed graph in a bounded degree graph
- Perfect domination and small cycles
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)
