Threshold dominating sets and an improved characterization of \(W[2]\)

DOI10.1016/S0304-3975(97)00101-1zbMath0912.68075OpenAlexW2055423880MaRDI QIDQ1274918

Michael R. Fellows, Rodney G. Downey

Publication date: 12 January 1999

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(97)00101-1

zbMATH Keywords

parameterized complexityBoolean circuitsdominating setsthreshold computationSatisfiability problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

The Turing way to parameterized complexity ⋮ An analysis of the W*-hierarchy ⋮ The Birth and Early Years of Parameterized Complexity ⋮ Parameterized complexity of generalized domination problems ⋮ Surfing with Rod ⋮ A generalization of Nemhauser and Trotter's local optimization theorem ⋮ The complexity of irredundant sets parameterized by size ⋮ Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles ⋮ Parameterized computational complexity of Dodgson and Young elections ⋮ Machine-based methods in parameterized complexity theory ⋮ Parameterized complexity of candidate control in elections and related digraph problems ⋮ Threshold dominating cliques in random graphs and interval routing ⋮ Parameterized Complexity of Candidate Control in Elections and Related Digraph Problems ⋮ Parameterized Algorithms for Generalized Domination ⋮ Perfect Code is \(W[1\)-complete] ⋮ Continuous facility location on graphs

Cites Work

• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Parameterized circuit complexity and the \(W\) hierarchy
• The parameterized complexity of sequence alignment and consensus
• On the parameterized complexity of short computation and factorization
• Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues]
• \(W[2\)-hardness of precedence constrained \(K\)-processor scheduling]
• Beyond NP-completeness for problems of bounded width (extended abstract)
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item