(Total) vector domination for graphs with bounded branchwidth

DOI10.1016/j.dam.2016.03.002zbMath1337.05082OpenAlexW2336746553MaRDI QIDQ290105

Yushi Uno, Toshimasa Ishii, Hirotaka Ono

Publication date: 1 June 2016

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2016.03.002

zbMATH Keywords

bounded branchwidthFPTmultiple dominating settotal vector dominating setvector dominating set

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (2)

Domination and convexity problems in the target set selection model ⋮ New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Implicit branching and parameterized partial cover problems
• On bounded-degree vertex deletion parameterized by treewidth
• Graph minors. X: Obstructions to tree-decomposition
• Call routing and the ratcatcher
• Which problems have strongly exponential complexity?
• On the existence of subexponential parameterized algorithms
• Graph minors. XIII: The disjoint paths problem
• Subexponential algorithms for partial cover problems
• On the approximability and exact algorithms for vector domination and related problems in graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• Algorithmic construction of sets for k -restrictions
• Hardness, Approximability, and Exact Algorithms for Vector Domination and Total Vector Domination in Graphs
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
• On the hardness of approximating minimization problems
• Constructive linear time algorithms for branchwidth
• On Dominating Sets and Independent Sets of Graphs
• Optimal branch-decomposition of planar graphs in O ( n ³ ) Time
• On the Relationship Between Clique-Width and Treewidth
• Latency-Bounded Target Set Selection in Social Networks
• Dynamic Programming and Fast Matrix Multiplication
• Parameterized Algorithms for Generalized Domination

This page was built for publication: (Total) vector domination for graphs with bounded branchwidth