文献

J-GLOBAL ID：202202217092518956   整理番号：22A0857864

有向Steiner経路カバーの計算【JST・京大機械翻訳】

Computing directed Steiner path covers

著者 (5件)： Gurski Frank (Institute of Computer Science, Heinrich Heine University Duesseldorf, Duesseldorf, Germany) ,  Komander Dominique (Institute of Computer Science, Heinrich Heine University Duesseldorf, Duesseldorf, Germany) ,  Rehs Carolin (Institute of Computer Science, Heinrich Heine University Duesseldorf, Duesseldorf, Germany) ,  Rethmann Jochen (Faculty of Electrical Engineering and Computer Science, Niederrhein University of Applied Sciences, Krefeld, Germany) ,  Wanke Egon (Institute of Computer Science, Heinrich Heine University Duesseldorf, Duesseldorf, Germany)
資料名： Journal of Combinatorial Optimization  (Journal of Combinatorial Optimization)
巻： 43  号： 2  ページ： 402-431  発行年： 2022年 
JST資料番号： W1143A  ISSN： 1382-6905  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 本論文では,有向グラフ上の指向Steiner Path Cover問題を考察した。有向グラフ[数式:原文を参照]といわゆる端末頂点のセット[数式:原文を参照]を考えて,この問題は,すべての末端頂点と最小数の非末端頂点(Steiner頂点)を含む頂点-素数単純有向経路の最小数を見つけることである。一次最小化基準は経路数である。有向グラフに対する最小Steiner経路カバーを線形時間で計算する方法を示した。これは,もし存在するならば,有向グラフ上の最適有向Steiner経路の線形時間計算を導く。Steiner経路問題はハミルトニアン経路問題を一般化するので,この結果は有向グラフ上の有向ハミルトニアン経路問題に対する最初の線形時間アルゴリズムを意味する。また,(有向)Steiner経路問題,および(指向)Steiner経路カバー問題に対して,(指向性)ハミルトニアン経路問題に対する二値整数プログラムを与えた。これらの整数プログラムは,電子産業における企業によって使用される,ピックアンドプレースマシンにおける変化時間を最小にするために使用することができる。Copyright The Author(s) 2021 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： ハミルトニアン ,  アルゴリズム ,  計画 ,  順路問題 ,  *有向グラフ ,  経路 ,  端末装置 ,  線形性 ,  指向性 ,  素数 ,  頂点 ,  被覆問題
準シソーラス用語： 組合せ最適化 ,  線形時間アルゴリズム ,  バイナリー , 【Automatic Indexing@JST】

著者キーワード (7件)： バイナリ整数プログラム ,  組合せ最適化 ,  有向コグラフ ,  有向Steiner経路被覆問題 ,  有向Steiner経路問題 ,  有向ハミルトニアン経路問題 ,  ピックアンドプレース機械

分類 (5件)： グラフ理論基礎  (IA02020S) ,  半導体集積回路  (NC03162T) ,  計算機網  (JC03000K) ,  計算理論  (JB02000A) ,  回路理論一般  (NA02010M)

タイトルに関連する用語 (2件)： 経路 ,  計算