文献

J-GLOBAL ID：201802266881551372   整理番号：18A0998682

グラフにおける距離保存消去順序付けについて:複雑性とアルゴリズム【JST・京大機械翻訳】

On distance-preserving elimination orderings in graphs: Complexity and algorithms

著者 (5件)： Coudert David (Universite Cote d’Azur, Inria, CNRS, I3S, France) ,  Ducoffe Guillaume (ICI - National Institute for Research and Development in Informatics, Romania) ,  Ducoffe Guillaume (The Research Institute of the University of Bucharest ICUB, Romania) ,  Nisse Nicolas (Universite Cote d’Azur, Inria, CNRS, I3S, France) ,  Soto Mauricio (Departamento de Ingenieria Matematica, Universidad de Chile, Facultad de Ciencias Fisicas y Matematicas, Chile)
資料名： Discrete Applied Mathematics  (Discrete Applied Mathematics)
巻： 243  ページ： 140-153  発行年： 2018年 
JST資料番号： A1227A  ISSN： 0166-218X  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： すべての連結グラフGに対して,GのサブグラフHは,Hにおける任意の2つの頂点間の距離が,Gと同様にHにおいて同じであるならば,等長である。Gの距離保存除去順序付けは,その頂点集合V(G)の全秩序化であり,(v1,v2,...,vn),1≦i<nの任意のサブグラフGi=G(v1,v2,...,vi)は等尺性である。この種の規則化は,弱いモジュラーグラフ(Chepoi,1998)に関する研究において,Chepoiによって導入された。著者らはNP完全であることを証明し,もしそれがほとんど2で直径を持つならば,そのような順序が与えられたグラフに対して存在するかどうかを決定することを証明した。次に,一つが存在するときの距離保存順序付けを計算する問題が,ツリー幅において固定パラメータ追跡可能であることを証明した。最後に,正確な指数時間アルゴリズムと問題に対するILP定式化に比較した場合に,距離保存順序付けを計算するための発見的手法について述べた。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 発見的方法 ,  グラフ理論 ,  定式化 ,  部分グラフ ,  *グラフ ,  *アルゴリズム
準シソーラス用語： 連結グラフ ,  *複雑性 ,  *順序づけ , 【Automatic Indexing@JST】

著者キーワード (6件)： 距離保存消去順序付け ,  計量グラフ理論 ,  NP完全 ,  正確な指数アルゴリズム ,  整数線形計画法 ,  有界ツリー幅

分類 (1件)： グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (6件)： グラフ ,  保存 ,  消去 ,  順序付け ,  複雑性 ,  アルゴリズム