文献

J-GLOBAL ID：202202274120149551   整理番号：22A1074716

Power版次数制限除去問題の近似について

On Approximation of Power Bounded Degree Deletion

著者 (2件)： MUKAEY Kento (Toyohashi Univ. Technol.) ,  FUJITO Toshihiro (Toyohashi Univ. Technol.)
資料名： 電子情報通信学会技術研究報告(Web)  (IEICE Technical Report (Web))
巻： 121  号： 407(COMP2021 31-39)  ページ： 36-41 (WEB ONLY)  発行年： 2022年02月27日 
JST資料番号： U2030A  ISSN： 2432-6380  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 次数制限除去問題(BDD)とは,頂点重み付き入力グラフの各頂点が次数制限を満たすように頂点を除去する際に,除去される頂点の重み和を最小化する問題である.そのpower版では,頂点重みの代わりに辺重みをもつグラフにおいて,各頂点にpowerを与えることで辺を除去する.ここで各辺は,その重み以上のpowerがいずれかの端点に与えられて初めて除去され,power BDDとは次数制限を満たすようにpowerを割り当て,その和を最小化する問題である.本発表では,power BDDが通常のBDDと同様に近似可能であることを示す.(著者抄録)

シソーラス用語： グラフ ,  *グラフ理論 ,  減少 ,  重みづけ ,  最小化問題 ,  *被覆問題 ,  集合 ,  *近似法
準シソーラス用語： 次数削減 ,  頂点被覆

分類 (2件)： 情報工学基礎理論一般  (JB01000T) ,  グラフ理論基礎  (IA02020S)

引用文献 (26件)：

• M. Okun and A. Barak, “A new approach for approximating node deletion problems,” Inform. Process. Lett., vol.88, no.5, pp.231-236, 2003. http://dx.doi.org/10.1016/j.ipl.2003.08.005
• R.M. Karp, “Reducibility among combinatorial problems,” Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972), pp.85-103, 1972.
• E. Angel, E. Bampis, V. Chau, and A. Kononov, “Min-power covering problems,” Algorithms and computation, vol.9472, pp.367-377, Lecture Notes in Comput. Sci., Springer, Heidelberg, 2015.
• M.R. Fellows, J. Guo, H. Moser, and R. Niedermeier, “A generalization of Nemhauser and Trotter’s local optimization theorem,” J. Comput. System Sci., vol.77, no.6, pp.1141-1158, 2011.
• I. Newman and C. Sohler, “Every property of hyperfinite graphs is testable,” SIAM J. Comput., vol.42, no.3, pp.1095-1112, 2013. https://doi.org/10.1137/120890946

タイトルに関連する用語 (4件)： 次数 ,  制限 ,  問題 ,  近似