文献

J-GLOBAL ID：202202289692617449   整理番号：22A1047253

直列並列グラフの連結ツリー幅を計算するための多項式時間アルゴリズム【JST・京大機械翻訳】

A polynomial time algorithm to compute the connected treewidth of a series-parallel graph

著者 (3件)： Mescoff Guillaume (LIRMM, Univ Montpellier, CNRS, Montpellier, France) ,  Paul Christophe (LIRMM, Univ Montpellier, CNRS, Montpellier, France) ,  Thilikos Dimitrios M. (LIRMM, Univ Montpellier, CNRS, Montpellier, France)
資料名： Discrete Applied Mathematics  (Discrete Applied Mathematics)
巻： 312  ページ： 72-85  発行年： 2022年 
JST資料番号： A1227A  ISSN： 0166-218X  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： グラフGのツリー幅がノード探索数に対応することはよく知られているが,そこでは,検索者のチームがラザイで見えない(あるいは,代わりにアジャイルで見える),そして,無限スピードで動く経路を通して移動する能力を持っている。最近,単調および接続ノード探索戦略が考慮されてきた。検索戦略は,もし,彼が exp出され,各ステップで,あるいは,探索者が占められた頂点の集合が,Gの連結部分グラフを誘発するならば,それが expedされ,接続されているので,再び,それが connecteditiveし,接続されるならば,モノトーンである。”その1つの検索戦略”は,単調である。”その場合,もし,各ステップにおいて,その集合は,また,その集合が,Gの接続された部分グラフを誘導する,という点である。グラフGの対応する接続および単調探索数は,根rを含むTの経路のノードに対応する袋の融合がGに接続される,根付きツリー分解(X,T,r)の最小幅として定義される,ctw(G)によって表される,連結木幅として表現できることを示した。本論文では,連結木幅のアルゴリズム的研究を開始した。O(n2logn)-時間動的計画法アルゴリズムを設計して,二連結直列並列グラフの連結木幅を計算した。実行時間における余分なn因子の価格において,著者らのアルゴリズムは,ほとんどの2つの木幅のグラフに一般化する。Copyright 2022 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *アルゴリズム ,  *グラフ ,  時間 ,  動的計画法 ,  部分グラフ ,  頂点 ,  チーム
準シソーラス用語： 木幅 ,  実行時間 ,  *多項式時間アルゴリズム ,  探索戦略 , 【Automatic Indexing@JST】

著者キーワード (8件)： グラフ分解 ,  グラフクラス ,  幅パラメータ ,  組合せアルゴリズム ,  直並列グラフ ,  ツリー幅 ,  連結ツリー幅 ,  動的計画法

分類 (2件)： グラフ理論基礎  (IA02020S) ,  人工知能  (JE08000Z)

タイトルに関連する用語 (4件)： 直列 ,  グラフ ,  計算 ,  多項式時間アルゴリズム