scientific article; zbMATH DE number 125608
From MaRDI portal
Publication:4027320
\(k\)-dominating set\(k\)-feedback vertex setalgorithmcompletenesscyclesfixed-parameter tractabilitygatesgraphindependent settree circuitweighted satisfiability
Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Recommendations
Cited in
(65)- On the parameterized complexity of multiple-interval graph problems
- On k-connectivity problems with sharpened triangle inequality
- Computational study on planar dominating set problem
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Fixed-parameter complexity in AI and nonmonotonic reasoning
- The many facets of upper domination
- Subexponential fixed-parameter algorithms for partial vector domination
- Solving large FPT problems on coarse-grained parallel machines
- Improving a fixed parameter tractability time bound for the shadow problem
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
- Exact algorithms for edge 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)
- The complexity of irredundant sets parameterized by size
- Faster deterministic \textsc{Feedback Vertex Set}
- On the complexity of the smallest grammar problem over fixed alphabets
- Parameterized algorithms and complexity for the traveling purchaser problem and its variants
- On the complexity of singly connected vertex deletion
- Domination chain: characterisation, classical complexity, parameterised complexity and approximability
- Exact crossing number parameterized by vertex cover
- Parameterized low-rank binary matrix approximation
- Inclusion/exclusion meets measure and conquer
- A fixed-parameter tractable algorithm for matrix domination
- Obtaining a planar graph by vertex deletion
- An improved parameterized algorithm for the independent feedback vertex set problem
- The parameterized complexity of maximality and minimality problems
- Sparse parameterized problems
- Parameterized counting problems
- Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits
- An algorithmic metatheorem for directed treewidth
- On the complexity landscape of the domination chain
- Algorithmic aspects of \textsc{Upper Domination}: a parameterised perspective
- (Total) vector domination for graphs with bounded branchwidth
- The birth and early years of parameterized complexity
- Vertex cover, dominating set and my encounters with parameterized complexity and Mike Fellows
- A basic parameterized complexity primer
- What's next? Future directions in parameterized complexity
- New analysis and computational study for the planar connected dominating set problem
- Algorithms and complexity of signed, minus, and majority domination
- A Linear Kernel for Planar Feedback Vertex Set
- Exact Algorithms for Edge Domination
- Iterative Compression for Exactly Solving NP-Hard Minimization Problems
- Interval Completion Is Fixed Parameter Tractable
- Parameterized complexity of generalized domination problems
- scientific article; zbMATH DE number 512804 (Why is no real title available?)
- scientific article; zbMATH DE number 512844 (Why is no real title available?)
- Confronting intractability via parameters
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Graphs with few \(P_4\)'s under the convexity of paths of order three
- Resolving conflicts for lower-bounded clustering
- On Geometric Set Cover for Orthants
- Triangles, 4-Cycles and Parameterized (In-)Tractability
- A parameterized algorithm for subset feedback vertex set in tournaments
- A survey of parameterized algorithms and the complexity of edge modification
- On approximation of multiple intruder locating domination number of a graph
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Advice classes of parametrized tractability
- Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy
- Parameterized complexity of (d, r)-domination via modular decomposition
- On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality
- Improved upper bounds for vertex cover
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- On generalizations of the shadow independent set problem
- On the parameterized complexity of dynamic problems
- Efficient algorithms for counting parameterized list H-colorings
- A cubic kernel for feedback vertex set and loop cutset
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)
