scientific article

Michael R. Fellows, Rodney G. Downey

Publication date: 21 February 1993

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

algorithm graph cycles completeness independent set fixed-parameter tractability gates \(k\)-dominating set weighted satisfiability \(k\)-feedback vertex set tree circuit

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (57)

An algorithmic metatheorem for directed treewidth ⋮ Solving large FPT problems on coarse-grained parallel machines ⋮ Improving a fixed parameter tractability time bound for the shadow problem ⋮ (Total) vector domination for graphs with bounded branchwidth ⋮ Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(\) and PSPACE analogues] ⋮ The Birth and Early Years of Parameterized Complexity ⋮ A Basic Parameterized Complexity Primer ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Fixed-parameter tractability of graph modification problems for hereditary properties ⋮ New analysis and computational study for the planar connected dominating set problem ⋮ Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization ⋮ On generalizations of the shadow independent set problem ⋮ Domination chain: characterisation, classical complexity, parameterised complexity and approximability ⋮ A parameterized algorithm for subset feedback vertex set in tournaments ⋮ A Linear Kernel for Planar Feedback Vertex Set ⋮ Exact Algorithms for Edge Domination ⋮ On the parameterized complexity of dynamic problems ⋮ Parameterized complexity of generalized domination problems ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Obtaining a planar graph by vertex deletion ⋮ Exact algorithms for edge domination ⋮ Unnamed Item ⋮ The many facets of upper domination ⋮ Exact crossing number parameterized by vertex cover ⋮ Special issues on The satisfiability problem (pp. 1--244) including papers from the 1st workshop on satisfiability, Certosa di Pontignano, Italy, April 29--May 3, 1996 and Boolean functions (pp. 245--479) ⋮ Parameterized low-rank binary matrix approximation ⋮ An improved parameterized algorithm for the independent feedback vertex set problem ⋮ Confronting intractability via parameters ⋮ Efficient algorithms for counting parameterized list \(H\)-colorings ⋮ The complexity of irredundant sets parameterized by size ⋮ Graphs with few \(P_4\)'s under the convexity of paths of order three ⋮ Fixed-parameter tractability and completeness II: On completeness for W[1] ⋮ Advice classes of parametrized tractability ⋮ Domination When the Stars Are Out ⋮ The parameterized complexity of maximality and minimality problems ⋮ Subexponential fixed-parameter algorithms for partial vector domination ⋮ Inclusion/exclusion meets measure and conquer ⋮ Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy ⋮ A cubic kernel for feedback vertex set and loop cutset ⋮ On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality ⋮ Improved upper bounds for vertex cover ⋮ Faster deterministic \textsc{Feedback Vertex Set} ⋮ On the Complexity Landscape of the Domination Chain ⋮ On the complexity of the smallest grammar problem over fixed alphabets ⋮ On the parameterized complexity of multiple-interval graph problems ⋮ On \(k\)-connectivity problems with sharpened triangle inequality ⋮ The Parameterized Complexity of Graph Cyclability ⋮ On Geometric Set Cover for Orthants ⋮ Algorithms and Complexity of Signed, Minus, and Majority Domination ⋮ Iterative Compression for Exactly Solving NP-Hard Minimization Problems ⋮ Algorithmic Aspects of Upper Domination: A Parameterised Perspective ⋮ Computational study on planar dominating set problem ⋮ Sparse parameterized problems ⋮ Parameterized algorithms and complexity for the traveling purchaser problem and its variants ⋮ On the complexity of singly connected vertex deletion ⋮ Parameterized counting problems ⋮ Fixed-parameter complexity in AI and nonmonotonic reasoning

This page was built for publication: