グラフ制約論理のための固定パラメータアルゴリズム【JST・京大機械翻訳】

Hatanaka Tatsuhiko; Hommelsheim Felix; Ito Takehiro; Kobayashi Yusuke; Muehlenthaler Moritz; Suzuki Akira

プレプリント

J-GLOBAL ID：202202200046567025 整理番号：22P0211359

グラフ制約論理のための固定パラメータアルゴリズム【JST・京大機械翻訳】

Fixed-Parameter Algorithms for Graph Constraint Logic

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

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

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

非決定論的制約論理(NCL)は,エッジ重みと頂点要求による制約グラフの方位に基づく計算の簡単なモデルである。NCLはPSPACE x空間を捕捉し,多くのパズル,ゲーム,および再構成問題のアルゴリズム硬度を証明するための有用なツールである。特に,その有用性は,重みの厳しい制限(例えば,エッジ重みの1つと2つだけ)と制約グラフの構造(例えば,有界帯域幅の平面および/またはx空間グラフ)の下でさえ,PSPACE完全のままであるという事実から生じる。制約グラフの構造に関するそのような制約は,NCLの表現性を制限するように見えないが,制約グラフのビルディングブロックは,表現性を失うことなく,制約グラフの重み-オンエッジ数および重み-2エッジ数,ならびに,アナント/またはx空間制約グラフのx空間またはx空間頂点の数のパラメータとして考慮されない。NCLはこれらのパラメータの任意のパラメータに対して固定パラメータ扱いやすい(FPT)ことを示した。特に,重み-オンエッジ数または空間頂点数によってパラメータ化されたNCLに対して,線形カーネルを得た。意味で,HarnとDemaineによって導入されたNCLは,PSPACEを捕捉する目的で最も経済的な方法で定義される。【JST・京大機械翻訳】

, , , , , , , , , ,
, , , , 【Automatic Indexing@JST】

グラフ理論基礎

, , , ,

前のページに戻る