文献

J-GLOBAL ID：201802270027422318   整理番号：18A0345556

三角形分割のためのCourcelleの定理【Powered by NICT】

Courcelle’s theorem for triangulations

著者 (2件)： Burton Benjamin A. (School of Mathematics and Physics, The University of Queensland, Brisbane, QLD 4072, Australia) ,  Downey Rodney G. (School of Mathematics, Statistics and Operations Research, Victoria University, New Zealand)
資料名： Journal of Combinatorial Theory. Series A  (Journal of Combinatorial Theory. Series A)
巻： 146  ページ： 264-294  発行年： 2017年 
JST資料番号： B0940A  ISSN： 0097-3165  CODEN： JCTHA  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： グラフ理論では,Courcelleの定理は,本質的に,アルゴリズム的問題は単項第二近似解論理における定式化できるならば,有界ツリー幅のグラフのための線形時間で解くことができることを示した。任意の固定次元の三角形分割,すべての三角形D多様体の一般的クラスに対するそのようなメタ定理を証明した:アルゴリズム問題は単項第二近似解論理で表現できるならば,その双対グラフは有界木幅を持つ三角形分割のための線形時間で解くことができる。3多様体トポロジーの結果を適用し,多くの困難な計算問題を設定が非常に少ないパラメータ化された複雑さの結果,木幅をパラメータとして実用的な関連性を持っている。メタ定理を用いて,それぞれ緊張角構造と離散Morse理論に固定パラメータ実行可能性結果を以前の回復と一般化,3多様体上の強力であるが複雑なTuraev-Viro不変量を計算するための新しい固定パラメータ実行可能性結果を証明した。Copyright 2018 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： 不変量 ,  グラフ理論 ,  パラメタリゼーション ,  線形性 ,  多様体 ,  定式化 ,  アルゴリズム ,  位相幾何学 ,  グラフ ,  *三角形分割
準シソーラス用語： Morse理論 ,  木幅 ,  複雑性 ,  近似解 , 【Automatic Indexing@JST】

著者キーワード (5件)： 三角形分割 ,  パラメータ化された複雑性 ,  多様体 ,  離散Morse理論 ,  Turaev-Viro不変量

分類 (3件)： 図形・画像処理一般  (JE04010I) ,  計算理論  (JB02000A) ,  グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (2件)： 三角形分割 ,  定理