文献

J-GLOBAL ID：201902289631659480   整理番号：19A2761462

平面グラフにおける最小フィードバック頂点集合のためのPTASのエンジニアリング【JST・京大機械翻訳】

Engineering a PTAS for Minimum Feedback Vertex Set in Planar Graphs

著者 (3件)： Borradaile Glencora (Oregon State University, Corvallis, OR, USA) ,  Le Hung (Oregon State University, Corvallis, OR, USA) ,  Zheng Baigong (Oregon State University, Corvallis, OR, USA)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 11544  ページ： 98-113  発行年： 2019年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 平衡分離器に基づく平面グラフにおける最適化問題に対する近似スキームの実用性を調べた。平面グラフにおける問題に対する最初の多項式時間近似スキーム(PTAS)は,平衡分離器に基づいており,グラフは,最適解がbruTe力あるいは他の方法により見出される十分に小さい部分に再帰的に分解される。しかしながら,この技術は,より現代的で(理論的に)より効率的な平面グラフを,最適解が動的計画法により見出される,有界の木幅のグラフに分解するより効率的な手法により想定された。後者のアプローチは実験的に試験されているが,前者のアプローチはそうではない。分離器に基づく方法を試験するために,平面グラフにおける最小フィードバック頂点集合(FVS)問題を調べた。平衡分離器と線形カーネルを用いたFVSに対する新しい簡単な[数式:原文を参照]時間近似スキームを提案した。線形カーネルは,グラフのサイズを最適解のサイズにおいて線形に減少させる。そうすることにおいて,著者らはFVSのためにBonamyとKowalikの線形カーネル[11]における縮小規則を修正した。このPTASを実装し,大規模合成および実世界平面グラフ上での性能を評価した。以前の平面PTAS工学結果[8,36]と異なり,著者らの実装は,すべてのテストしたグラフに関する理論的誤差限界を保証した。Copyright 2019 Springer Nature Switzerland AG Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 近似法 ,  線形性 ,  *平面グラフ ,  最適化問題 ,  分離装置 ,  動的計画法 ,  *グラフ
準シソーラス用語： グラフアルゴリズム ,  誤差限界 ,  木幅 ,  有界 ,  最適解 ,  多項式時間 ,  実用性 ,  *フィードバック頂点集合 , 【Automatic Indexing@JST】

著者キーワード (4件)： フィードバック頂点集合 ,  平面グラフアルゴリズム ,  近似スキーム ,  アルゴリズム工学

分類 (2件)： 分子・遺伝情報処理  (JE15040B) ,  計算理論  (JB02000A)

タイトルに関連する用語 (3件)： 平面グラフ ,  フィードバック頂点集合 ,  エンジニアリング