| Presentation | 2014/6/6 (Total) Vector Domination for Graphs with Bounded Branchwidth TOSHIMASA ISHII, HIROTAKA ONO, YUSHI UNO, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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 c 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | |
| Paper # | |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2014/6/6(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | (Total) Vector Domination for Graphs with Bounded Branchwidth |
| Sub Title (in English) | |
| Keyword(1) | |
| 1st Author's Name | TOSHIMASA ISHII |
| 1st Author's Affiliation | Graduate School of Economics and Business Administration, Hokkaido University() |
| 2nd Author's Name | HIROTAKA ONO |
| 2nd Author's Affiliation | Department of Economic Engineering, Faculty of Economics, Kyushu University |
| 3rd Author's Name | YUSHI UNO |
| 3rd Author's Affiliation | Department of Mathematics and Information Sciences, Graduate School of Science, Osaka Prefecture University |
| Date | 2014/6/6 |
| Paper # | |
| Volume (vol) | vol.114 |
| Number (no) | 80 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |