(Total) Vector Domination for Graphs with Bounded Branchwidth

スポンサーリンク

概要

• 論文の詳細を見る

• Given a graph G = (V, E) of order n and an n-dimensional non-negative vector d = (d(1), d(2),..., d(n)), called demand vector, the vector domination (resp., total vector domination) is the problem of finding a minimum S ⊆ V such that every vertex v in V ＼ S (resp., in V) has at least d(v) neighbors in S . The (total) vector domination is a generalization of many dominating set type problems, e.g., the dominating set problem, the k-tuple dominating set problem (this k is different from the solution size), and so on, and its approximability and inapproximability have been studied under this general framework. In this paper, we show that a (total) vector domination of graphs with bounded branchwidth can be solved in polynomial time. This implies that the problem is polynomially solvable also for graphs with bounded treewidth. Consequently, the (total) vector domination problem for a planar graph is subexponential fixed-parameter tractable with respect to k, where k is the size of solution.

• 2014-06-06

著者

• Hirotaka Ono

  Department Of Economic Engineering Kyushu University.

• Yushi Uno

  Department Of Mathematics And Information Sciences Graduate School Of Science Osaka Prefecture Unive

• Toshimasa Ishii

  Graduate School of Economics and Business Administration, Hokkaido University

• Hirotaka Ono

  Department of Economic Engineering, Faculty of Economics, Kyushu University

関連論文

• The Complexity of Free Flood Filling Games
• Approximating the path-distance-width for k-cocomparability graphs
• (Total) Vector Domination for Graphs with Bounded Branchwidth

スポンサーリンク