文献

J-GLOBAL ID：201902224991195637   整理番号：19A1540570

二基準時間経路の列挙について【JST・京大機械翻訳】

On the Enumeration of Bicriteria Temporal Paths

著者 (2件)： Mutzel Petra (Department of Computer Science, TU Dortmund University, Dortmund, Germany) ,  Oettershagen Lutz (Department of Computer Science, TU Dortmund University, Dortmund, Germany)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 11436  ページ： 518-535  発行年： 2019年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 重み付き時間グラフにおける経路列挙の複雑さを論じた。重み付き時間グラフにおいて,各エッジは利用可能時間,横断時間,およびいくつかのコストを有する。著者らは,著者らが低コストと短期間または初期到着時間を有するすべての効率的経路の集合に関心を持つ2つの二基準時間的最小コスト経路問題を導入した。残念ながら,効率的経路の数は入力のサイズにおいて指数関数的である。しかし,厳密に正のエッジコストの場合には,多項式時間遅れと多項式空間を持つ効率的な経路の集合を列挙するアルゴリズムを提供することができる。著者らがパレート最適解(経路自体ではない)の集合にのみ興味がある場合には,非負エッジコストの場合,これらの集合が多項式時間で見出されることを示した。さらに,各パレート最適解に対して,多項式時間で効率的な経路を見出すことができる。Copyright 2019 Springer Nature Switzerland AG Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 指数関数 ,  グラフ ,  *多項式 ,  アルゴリズム ,  順路問題
準シソーラス用語： 多項式時間 ,  到着時間 ,  ローコスト , 【Automatic Indexing@JST】

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

タイトルに関連する用語 (1件)： 経路