文献

J-GLOBAL ID：201902264848486925   整理番号：19A1392832

線セグメントを持つ被覆セルの近似可能性【JST・京大機械翻訳】

Approximability of covering cells with line segments

著者 (4件)： Carmi Paz (Department of Computer Science, Ben-Gurion University of the Negev, Beer-Sheva, Israel) ,  Maheshwari Anil (School of Computer Science, Carleton University, Ottawa, Canada) ,  Mehrabi Saeed (School of Computer Science, Carleton University, Ottawa, Canada) ,  Xavier da Silveira Luis Fernando Schultz (School of Computer Science and Electrical Engineering, University of Ottawa, Ottawa, Canada)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 784  ページ： 133-141  発行年： 2019年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： Kormanらは以下の幾何学的被覆問題を研究した。すなわち,平面におけるn線セグメントの集合Sを与えて,線セグメントの配置におけるあらゆるセルがカバーされるように,最小数の線セグメントを発見した。ここでは,sがfに入射するならば,ラインセグメントはセルfをカバーする。この問題は,Sにおける線セグメントが軸平行であるとしてもNP困難であることを示し,目標が「長方形」セル(すなわち,正確に4軸平行線セグメントにより定義されるセル)をカバーすることを目標とするときNP困難である。本論文では,この問題の近似性を考察した。最初に,Sにおける線セグメントが任意の方向にあるときに,問題に対するPTASを与えた。しかし,著者らは,1つの方向からカバー線セグメントを選択することができた。次に,著者らは,目標が水平および垂直線セグメントの両方から線セグメントを用いて長方形セルをカバーすることであるとき,この問題がAPX困難であることを示した。また,問題のパラメータ化された複雑さを考慮し,最適解のサイズによってパラメータ化されるとき,問題がFPTであることを証明する。著者らのFPTアルゴリズムは,Sにおけるラインセグメントが2つの方向を持ち,ゴールがすべてのセルをカバーするために動作し,その中でゴールが「長方形」セルをカバーすることを目的としている。Copyright 2019 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： NP困難 ,  パラメタリゼーション ,  *近似法 ,  アルゴリズム ,  *被覆 ,  類似性 ,  パラメータ ,  被覆問題
準シソーラス用語： 最適解 , 【Automatic Indexing@JST】

著者キーワード (6件)： 幾何学的被覆 ,  ラインセグメントカバー ,  近似アルゴリズム ,  APX硬度 ,  PTAS ,  固定パラメータ追跡可能性

分類 (2件)： グラフ理論基礎  (IA02020S) ,  図形・画像処理一般  (JE04010I)

タイトルに関連する用語 (4件)： セグメント ,  セル ,  近似 ,  可能性