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

Mescoff Guillaume; Paul Christophe; Thilikos Dimitrios

プレプリント

J-GLOBAL ID：202202209723858438 整理番号：21P0028096

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

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

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (3件)： , ,
資料名：
発行年： 2020年04月01日プレプリントサーバーでの情報更新日： 2021年01月27日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

グラフGのツリー幅がノード探索数に対応し,コップのチームがラザイ,可視的であり,無限速度で移動する能力を持っている。最近の論文では,接続ノード探索戦略を考察した。各ステップで,コップのチームによって占有された頂点の集合が,Gの接続部分グラフを誘発するならば,探索ストライギーを接続する。グラフGの接続された探索数は,根rを含むTの経路のノードに対応する袋の融合が接続されるような,根付きツリー分解(ΔΨX},T,r}の最小幅として定義される,連結木幅として表現される。明らかに,tw(G)≦slanctw(G)であった。本論文では,連結木幅のアルゴリズム的研究を開始した。O(n ̄2logn)-時間動的計画法アルゴリズムを設計し,二連結直列並列グラフの連結木幅を計算した。走行時間における余分のn因子の価格において,著者らのアルゴリズムは,ほとんどの2で木幅のグラフを genす。【JST・京大機械翻訳】

, ,
, , , 【Automatic Indexing@JST】

グラフ理論基礎

, , ,

前のページに戻る