文献

J-GLOBAL ID：202102256543362765   整理番号：21A0692015

小物に目を置く方法【JST・京大機械翻訳】

How to Keep an Eye on Small Things

著者 (2件)： Nilsson Bengt J. (Department of Computer Science, Malmo University, SE-205 06 Malmo, Sweden) ,  Zylinski Pawel (Institute of Informatics, University of Gdansk, 80-308 Gdansk, Poland)
資料名： International Journal of Computational Geometry & Applications  (International Journal of Computational Geometry & Applications)
巻： 30  号： 2  ページ： 97-120  発行年： 2020年 
JST資料番号： W0385A  ISSN： 0218-1959  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： シンガポール (SGP)  言語： 英語 (EN)

抄録/ポイント： 多角形に対する2種類の保護問題に関する新しい結果を示した。最初の問題に対して,nエッジを持つ簡単な多角形において与えられた最短経路をガードする点の最小集合を計算するための最適線形時間アルゴリズムを提案した。また,穴を持つ多角形において,多項式時間アルゴリズムが[数式:原文を参照]の近似因子内で問題を解決できないように,P=NPがなければ,一定の[数式:原文を参照]が存在することを証明した。2番目の問題に対して,h穴を持つ多角形においてk指定点を見る最短トルーを計算するための[数式:原文を参照]-FPTアルゴリズムを提案した。また,近似因子2を持つこの問題に対するk-FPT近似アルゴリズムを提案した。さらに,一般的な問題は,P[数式:原文を参照]NPがなければ,いくつかの一定の[数式:原文を参照]に対して,[数式:原文を参照]の因子よりも多項式的に近似できないことを証明した。Copyright 2021 World Scientific Publishing Company All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  多項式 ,  *近似法
準シソーラス用語： 近似アルゴリズム ,  線形時間アルゴリズム ,  多項式時間アルゴリズム ,  最短経路 , 【Automatic Indexing@JST】

著者キーワード (4件)： 視界 ,  保護 ,  近似アルゴリズム ,  FPTアルゴリズム

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