木における消防士問題に対する近似アルゴリズムの改良

岩井川裕; 神山直之; 松井知己

文献

J-GLOBAL ID：201002255721115225 整理番号：10A0772195

木における消防士問題に対する近似アルゴリズムの改良

Improved Approximation Algorithms for Firefighter Problem on Trees

出版者サイト複写サービスで全文入手 {{ this.onShowCLink("http://jdream3.com/copy/?sid=JGLOBAL&noSystem=1&documentNoArray=10A0772195&COPY=1") }}
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=10A0772195&from=J-GLOBAL&jstjournalNo=S0532B") }}

著者 (3件)： , ,
資料名：
巻： 110 号： 104(COMP2010 15-23) ページ： 9-12 発行年： 2010年06月18日
JST資料番号： S0532B ISSN： 0913-5685 資料種別：会議録 (C)
記事区分：原著論文発行国：日本 (JPN) 言語：日本語 (JA)

消防士問題は火災の延焼,伝染病,そしてコンピューターウイルスの拡散等をモデル化した問題である。本論文では根付き木上の消防士問題を扱う。消防士問題は最大次数が3の根付き木上に限定してもNP困難であることが知られている。本論文では,既存の近似アルゴリズムの近似率を改善する手法を2つ提案する。まず最初に,陰的列挙を用いた手法を提案する。この手法を既存の(1-1/e)-近似アルゴリズムに適用すると,(1-(k-1)/((K-1)e+1))-近似アルゴリズムが得られる。ただし,kは根の子供の数を表している。例えば3分木の場合は,k=3であるので近似率は(1-(k-1)/((K-1)e+1)))≧0.6892となり,既存の近似率1-1/e≒0.6321より良い値となっている。2つめの手法は,3分木に限定した改善手法であり,帰納的な考え方を用いている。この手法を既存の(1-1/e)-近似に用いると,0.6976-近似アルゴリズムが得られる。これら2つの手法を併用すると,3分木における消防士問題に対する0.7144-近似アルゴリズムを構築することができる。(著者抄録)

, , , ,
, ,

計算理論 , 数値解析,近似法

引用文献 (5件)：

ANSHELEVICH, E. Approximation algorithms for the firefighter problem : Cuts over time and submodularity. Proc. the 20th International Symposium on Algorithms and Computation (ISAAC'09). 2009, 974-983
CAI, L. Firefighting on trees : (1-1/e)-approximation, fixed parameter tractability and a subexponential algorithm. Proc. the 19th International Symposium on Algorithms and Computation (ISAAC'08). 2008, 258-269
FINBOW, S. The firefighter problem for graphs of maximum degree three. Discrete Mathematics. 2007, 307, 16, 2094-2105
HARTNELL, B. Firefighter! An application of domination. the 24th Manitoba Conference on Combinatorial Mathematics and Computing, University of Minitoba, Winnipeg, Cadada, 1995. 1995
HARTNELL, B. Firefighting on trees : How bad is the greedy algorithm?. Congressus Numerantium. 2000, 145, 187-192

, ,

前のページに戻る