scientific article; zbMATH DE number 125608
From MaRDI portal
Publication:4027320
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)
Recommendations
Cited in
(63)- Algorithms and complexity of signed, minus, and majority domination
- Sparse parameterized problems
- Parameterized counting problems
- Bounded fixed-parameter tractability and \(\log^{2}n\) nondeterministic bits
- Parameterized complexity in multiple-interval graphs: domination, partition, separation, irredundancy
- An algorithmic metatheorem for directed treewidth
- A parameterized algorithm for subset feedback vertex set in tournaments
- Fixed-Parameter Tractability and Completeness I: Basic Results
- A Linear Kernel for Planar Feedback Vertex Set
- Iterative Compression for Exactly Solving NP-Hard Minimization Problems
- Parameterized complexity of generalized domination problems
- What's next? Future directions in parameterized complexity
- The birth and early years of parameterized complexity
- Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
- A basic parameterized complexity primer
- The parameterized complexity of maximality and minimality problems
- 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
- (Total) vector domination for graphs with bounded branchwidth
- Subexponential fixed-parameter algorithms for partial vector domination
- On k-connectivity problems with sharpened triangle inequality
- 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
- Advice classes of parametrized tractability
- Improving a fixed parameter tractability time bound for the shadow problem
- On the complexity landscape of the domination chain
- On generalizations of the shadow independent set problem
- An improved parameterized algorithm for the independent feedback vertex set problem
- On the complexity of the smallest grammar problem over fixed alphabets
- A survey of parameterized algorithms and the complexity of edge modification
- On the parameterized complexity of multiple-interval graph problems
- Obtaining a planar graph by vertex deletion
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
- Triangles, 4-Cycles and Parameterized (In-)Tractability
- New analysis and computational study for the planar connected dominating set problem
- Domination chain: characterisation, classical complexity, parameterised complexity and approximability
- Exact crossing number parameterized by vertex cover
- A cubic kernel for feedback vertex set and loop cutset
- Confronting intractability via parameters
- Algorithmic aspects of \textsc{Upper Domination}: a parameterised perspective
- Exact Algorithms for Edge Domination
- Efficient algorithms for counting parameterized list H-colorings
- Computational study on planar dominating set problem
- On Geometric Set Cover for Orthants
- 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
- 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)
- Faster deterministic \textsc{Feedback Vertex Set}
- Parameterized algorithms and complexity for the traveling purchaser problem and its variants
- scientific article; zbMATH DE number 512844 (Why is no real title available?)
- Vertex cover, dominating set and my encounters with parameterized complexity and Mike Fellows
- A fixed-parameter tractable algorithm for matrix domination
- Exact algorithms for edge domination
- Inclusion/exclusion meets measure and conquer
- The complexity of irredundant sets parameterized by size
- Resolving conflicts for lower-bounded clustering
- On approximation of multiple intruder locating domination number of a graph
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)
