文献

J-GLOBAL ID：201902223765763826   整理番号：19A1476568

半順序集合の次元を求める固定パラメータアルゴリズム

Parameterized Algorithms for Order Dimension

著者 (1件)： 小林靖明 (京大)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 119  号： 21(COMP2019 1-9)(Web)  ページ： 91-95 (WEB ONLY)  発行年： 2019年05月03日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 半順序集合の次元は半順序集合の複雑さを表すもっとも基本的なパラメータのひとつである.与えられた半順序集合の次元を計算する問題を考える.次元がk以下であるかどうかを判定する問題はk≧3においてNP完全であることが知られている.本稿では,半順序集合から得られるグラフの構造に関するパラメータを考えたとき,固定パラメータ容易となるようなパラメータについて考察する.(著者抄録)

シソーラス用語： 半順序 ,  *集合 ,  *次元 ,  パラメータ ,  構造 ,  *NP完全問題 ,  性質
準シソーラス用語： NP完全 ,  グラフ構造 ,  複雑性

分類 (1件)： その他の情報工学基礎理論  (JB06000C)

引用文献 (11件)：

• H. L. Bodlaender: A tourist guide through treewidth. Acta Cybernetica 11(1-2), 1-22 (1993)
• B. Courcelle: The monadic second order theory of Graph I: Recognisable sets of finite graphs. Information and Computation 85, 12-75 (1990)
• B. Dushnik, E. W. Miller: Partially ordered sets. American Journal of Mathematics 63(3), 600-610 (1941)
• E. Eiben, R. Ganian, K. Kangas, S. Ordyniak: Counting Linear Extensions: Parameterizations by Treewidth. Algorithmica, 1-27 (2018)
• T. Hiraguchi: On the dimension of orders. Science Reports of Kanazawa University 4, 1-20 (1995)

タイトルに関連する用語 (3件)： 次元 ,  パラメータ ,  アルゴリズム