文献

J-GLOBAL ID：201702286358099823   整理番号：17A1419610

外平面直径改善のための多項式時間アルゴリズム【Powered by NICT】

A polynomial-time algorithm for Outerplanar Diameter Improvement

著者 (9件)： Cohen Nathann (CNRS, LRI, Orsay, France) ,  Goncalves Daniel (CNRS, LIRMM, Montpellier, France) ,  Kim Eun Jung (CNRS, LAMSADE, Paris, France) ,  Paul Christophe (CNRS, LIRMM, Montpellier, France) ,  Sau Ignasi (CNRS, LIRMM, Montpellier, France) ,  Thilikos Dimitrios M. (CNRS, LIRMM, Montpellier, France) ,  Thilikos Dimitrios M. (Computer Technology Institute and Press “Diophantus”, Patras, Greece) ,  Thilikos Dimitrios M. (Department of Mathematics, University of Athens, Athens, Greece) ,  Weller Mathias (CNRS, LIRMM, Montpellier, France)
資料名： Journal of Computer and System Sciences  (Journal of Computer and System Sciences)
巻： 89  ページ： 315-327  発行年： 2017年 
JST資料番号： B0861A  ISSN： 0022-0000  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 外平面直径改善問題は,グラフGと整数Dを与えられた,得られたグラフが外平面であり,多くの直径を有するGにエッジを付加することができるかどうかを問うた。多項式時間においてこの問題を解く動的計画法アルゴリズムを提案した。外平面直径改善は有名な挑戦的な平面直径改善問題へのいくつかの構造類似体を示し,得られたグラフは,代わりに,平面である。この後者の問題の複雑性状態である。Copyright 2017 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： 動的計画法 ,  *アルゴリズム ,  グラフ ,  類似物質
準シソーラス用語： 複雑性 ,  *多項式時間 ,  *多項式時間アルゴリズム , 【Automatic Indexing@JST】

著者キーワード (5件)： 直径改善 ,  外平面グラフ ,  仕上げ問題 ,  多項式時間アルゴリズム ,  動的計画法

分類 (1件)： 計算理論  (JB02000A)

タイトルに関連する用語 (2件)： 直径 ,  多項式時間アルゴリズム