(Total) vector domination for graphs with bounded branchwidth

DOI10.1016/J.DAM.2016.03.002MaRDI QIDQ290105zbMATH OpenOpenAlexFDO

Authors Toshimasa Ishii, Hirotaka Ono, Yushi Uno

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

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

Recommendations

• (Total) vector domination for graphs with bounded branchwidth
• Subexponential fixed-parameter algorithms for partial vector domination
• Hardness, approximability, and exact algorithms for vector domination and total vector domination in graphs
• Subexponential fixed-parameter algorithms for partial vector domination
• On the approximability and exact algorithms for vector domination and related problems in graphs

Cites work

• scientific article; zbMATH DE number 125608 (Why is no real title available?)
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• scientific article; zbMATH DE number 1792607 (Why is no real title available?)
• Algorithmic construction of sets for k -restrictions
• Call routing and the ratcatcher
• Constructive linear time algorithms for branchwidth
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• Dynamic Programming and Fast Matrix Multiplication
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• Graph minors. X: Obstructions to tree-decomposition
• Graph minors. XIII: The disjoint paths problem
• Hardness, approximability, and exact algorithms for vector domination and total vector domination in graphs
• Implicit branching and parameterized partial cover problems
• Latency-bounded target set selection in social networks
• On Dominating Sets and Independent Sets of Graphs
• On bounded-degree vertex deletion parameterized by treewidth
• On the Relationship Between Clique-Width and Treewidth
• On the approximability and exact algorithms for vector domination and related problems in graphs
• On the existence of subexponential parameterized algorithms
• On the hardness of approximating minimization problems
• Optimal branch-decomposition of planar graphs in \(O(n^3)\) time
• Parameterized Algorithms for Generalized Domination
• Subexponential algorithms for partial cover problems
• Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Which problems have strongly exponential complexity?
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data

Cited in

(7)

• (Total) vector domination for graphs with bounded branchwidth
• Subexponential fixed-parameter algorithms for partial vector domination
• Subexponential fixed-parameter algorithms for partial vector domination
• Hardness, approximability, and exact algorithms for vector domination and total vector domination in graphs
• On the approximability and exact algorithms for vector domination and related problems in graphs
• New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs
• Domination and convexity problems in the target set selection model

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q290105)