An FPT-algorithm for modifying a graph of bounded treewidth to decrease the size of its dominating set using minimum modification

DOI10.1016/j.ipl.2016.04.002zbMath1357.68088OpenAlexW2333243216MaRDI QIDQ284360

Mehdy Roayaei, Mohammadreza Razzazi

Publication date: 18 May 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2016.04.002

zbMATH Keywords

computational complexitytree decompositiondominating setfixed-parameter tractability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Treewidth. Computations and approximations
• Dominating sets for convex functions with some applications
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
• Partial vs. Complete Domination: t-Dominating Set
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: An FPT-algorithm for modifying a graph of bounded treewidth to decrease the size of its dominating set using minimum modification