scientific article
From MaRDI portal
Publication:4027320
zbMATH Open0768.68136MaRDI QIDQ4027320FDOQ4027320
Michael R. Fellows, Rodney G. Downey
Publication date: 21 February 1993
Title of this publication is not available (Why is that?)
graphalgorithmcompletenesscyclesfixed-parameter tractabilityindependent setgates\(k\)-dominating setweighted satisfiability\(k\)-feedback vertex settree circuit
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cited In (61)
- On approximation of multiple intruder locating domination number of a graph
- A parameterized algorithm for subset feedback vertex set in tournaments
- Sparse parameterized problems
- Parameterized counting problems
- Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits
- The Parameterized Complexity of Graph Cyclability
- Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy
- An algorithmic metatheorem for directed treewidth
- A Linear Kernel for Planar Feedback Vertex Set
- What’s Next? Future Directions in Parameterized Complexity
- Iterative Compression for Exactly Solving NP-Hard Minimization Problems
- Parameterized complexity of generalized domination problems
- Domination When the Stars Are Out
- The parameterized complexity of maximality and minimality problems
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality
- Improved upper bounds for vertex cover
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Subexponential fixed-parameter algorithms for partial vector domination
- (Total) vector domination for graphs with bounded branchwidth
- On \(k\)-connectivity problems with sharpened triangle inequality
- Algorithms and Complexity of Signed, Minus, and Majority Domination
- Solving large FPT problems on coarse-grained parallel machines
- On the parameterized complexity of dynamic problems
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Parameterized low-rank binary matrix approximation
- Improving a fixed parameter tractability time bound for the shadow problem
- Advice classes of parametrized tractability
- On generalizations of the shadow independent set problem
- A survey of parameterized algorithms and the complexity of edge modification
- The Birth and Early Years of Parameterized Complexity
- An improved parameterized algorithm for the independent feedback vertex set problem
- A Basic Parameterized Complexity Primer
- On the complexity of the smallest grammar problem over fixed alphabets
- Obtaining a planar graph by vertex deletion
- On the parameterized complexity of multiple-interval graph problems
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
- Domination chain: characterisation, classical complexity, parameterised complexity and approximability
- Exact crossing number parameterized by vertex cover
- New analysis and computational study for the planar connected dominating set problem
- A cubic kernel for feedback vertex set and loop cutset
- Confronting intractability via parameters
- Title not available (Why is that?)
- Exact Algorithms for Edge Domination
- On the Complexity Landscape of the Domination Chain
- Efficient algorithms for counting parameterized list \(H\)-colorings
- On Geometric Set Cover for Orthants
- Computational study on planar dominating set problem
- Interval Completion Is Fixed Parameter Tractable
- On the complexity of singly connected vertex deletion
- Fixed-parameter complexity in AI and nonmonotonic reasoning
- Graphs with few \(P_4\)'s under the convexity of paths of order three
- Algorithmic Aspects of Upper Domination: A Parameterised Perspective
- The many facets of upper domination
- 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)
- Title not available (Why is that?)
- Faster deterministic \textsc{Feedback Vertex Set}
- Parameterized algorithms and complexity for the traveling purchaser problem and its variants
- Exact algorithms for edge domination
- Inclusion/exclusion meets measure and conquer
- The complexity of irredundant sets parameterized by size
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4027320)
