抄録/ポイント:
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
ツリー幅のような分解パラメータは一般にNP困難グラフ問題に対する固定パラメータアルゴリズムを得るために用いられる。ツリー幅によってパラメータ化されたW[1]困難である問題のために,自然な代替案は,頂点分離器の代わりにエッジカットに基づくツリー幅の適切なアナログを使用することである。ツリーカット幅がエッジカットの木幅の類似点としてコインされたが,そのアルゴリズム応用は,しばしば,エッジカットベースアナログによってパラメータ化された固定パラメータ扱いやすさをツリー幅に期待する12問題から,ツリーカット幅によってパラメータ化されたW[1]ハードであると,そのアルゴリズム応用は,しばしば,結果に導き出される。”1つは,木-カット幅によってパラメータ化されたW[1]-ハードである事を示したものである。”そのアルゴリズム的応用”は,しばしば,非点滅的結果に繋がった。”そのアルゴリズム的応用”は,木-切断幅によってパラメータ化された固定パラメータトライラビリティを期待する,という事をしばしば導く。主な貢献として,エッジカット幅と呼ばれるツリー幅に対するエッジカットベースアナログを開発した。エッジカット幅は,グラフのスパニング木を通過するサイクルの密度の測定に基づいて,直感的にである。その利益は,比較的単純な定義だけでなく,主に興味深いアルゴリズム特性を持ち,それは,固定パラメータアルゴリズムによって計算することができ,そして,それは,ツリーカット幅がそうでなくなるすべての前述の問題に対して,固定パラメータアルゴリズムをもたらした。【JST・京大機械翻訳】