文献

J-GLOBAL ID：201402258146783529   整理番号：14A0891223

有界枝幅を有するグラフの(全)ベクトル支配

(Total) Vector Domination for Graphs with Bounded Branchwidth

著者 (3件)： ISHII Toshimasa (Hokkaido Univ., Sapporo, JPN) ,  ONO Hirotaka (Kyushu Univ., Fukuoka, JPN) ,  UNO Yushi (Osaka Prefecture Univ., Sakai, JPN)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 114  号： 80(COMP2014 8-14)  ページ： 1-8  発行年： 2014年06月06日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 需要ベクトルと呼ばれる,次数n,n次元非負ベクトルd=(d(1),d(2),...,d(n))のグラフG=(V,E)を所与として,ベクトル支配(各,全ベクトル支配)はV\S(各,Vにおける)のどの頂点vも少なくともSのd(v)近傍を持つような最小S⊆Vを発見する問題である。(全)ベクトル支配は多くの支配型問題,例えば,支配集合問題,kチュープル支配集合問題(このkは解サイズとは異なる)などの一般化であり,その近似可能性と非近似可能性がこの一般フレームワークにおいて研究されてきた。本論文では,有界枝幅を有するグラフの(全)ベクトル支配が多項式時間で解けることを示した。このことは,有界ツリー幅を有するグラフについても問題を多項式時間で解けることを意味する。従って,平面グラフの(全)ベクトル支配問題はkに関して部分指数一定パラメータとして扱いやすく,kは解のサイズである。(翻訳著者抄録)

シソーラス用語： 幅 ,  *グラフ理論 ,  境界 ,  木【グラフ】 ,  *枝分れ ,  *ベクトル ,  パラメータ ,  問題解決 ,  平面グラフ ,  定理 ,  頂点 ,  集合 ,  *計算理論
準シソーラス用語： 一定パラメータトラクタビリティ ,  支配集合 ,  枝【グラフ】 ,  多項式時間 ,  有界ツリー幅

分類 (2件)： 計算理論  (JB02000A) ,  グラフ理論基礎  (IA02020S)

引用文献 (30件)：

• Alon, N., Moshkovitz, D. and Safra, S.: Algorithmic construction of sets for k-restrictions, ACM Transactions on Algorithms (TALG), Vol. 2, No. 2, pp. 153-177 (2006).
• Amini, O., Fomin, F. V. and Saurabh, S.: Implicit branching and parameterized partial cover problems, Journal of Computer and System Sciences, Vol. 77, No. 6, pp. 1159-1171 (2011).
• Betzler, N., Bredereck, R., Niedermeier, R. and Uhlmann, J.: On bounded-degree vertex deletion parameterized by treewidth, Discrete Applied Mathematics, Vol. 160, No. 1, pp. 53-60 (2012).
• Bodlaender, H. L. and Thilikos, D. M.: Constructive linear time algorithms for branchwidth, Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 1256, Springer, pp. 627-637 (1997).
• Cai, L. and Juedes, D.: On the existence of subexponential parameterized algorithms, Journal of Computer and System Sciences, Vol. 67, No. 4, pp. 789-807 (2003).

タイトルに関連する用語 (5件)： 有界 ,  枝 ,  グラフ ,  ベクトル ,  支配