| 講演名 | 2019-05-11 半順序集合の次元を求める固定パラメータアルゴリズム 小林 靖明(京大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 半順序集合の{em 次元}は半順序集合の複雑さを表すもっとも基本的なパラメータのひとつである．与えられた半順序集合の次元を計算する問題を考える．次元が$k$以下であるかどうかを判定する問題は$k ge 3$においてNP完全であることが知られている．本稿では，半順序集合から得られるグラフの構造に関するパラメータを考えたとき，固定パラメータ容易となるようなパラメータについて考察する． |
| 抄録(英) | The {em dimension} of a partially ordered set (poset) is known to be one of the fundamental complexity measures of posets. We consider the problem of computing the dimention of posets. It is known that the problem of deciding if the dimension of a given poset is at most $k$ is NP-complete for any fixed $k ge 3$. In this paper, we consider structural parameterizations of graphs obtained from a given poset and show the fixed-parameter tractability results with respect to well-known graph parameters. |
| キーワード(和) | 半順序集合 / 次元 / 固定パラメータアルゴリズム / 木幅 |
| キーワード(英) | partially ordered set / dimension / fixed-parameter algorithm / treewidth |
| 資料番号 | COMP2019-8 |
| 発行日 | 2019-05-03 (COMP) |
| 研究会情報 | |
| 研究会 | COMP / IPSJ-AL |
|---|---|
| 開催期間 | 2019/5/10(から2日開催) |
| 開催地（和） | 熊本大学 |
| 開催地（英） | Kumamoto University |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | 藤戸 敏弘(豊橋技科大) / 瀧本 英二(九州大学) |
| 委員長氏名（英） | Toshihiro Fujito(Toyohashi Univ. of Tech.) / 瀧本 英二(九州大学) |
| 副委員長氏名（和） | 中野 眞一(群馬大) |
| 副委員長氏名（英） | Shinichi Nakano(Gunma Univ.) |
| 幹事氏名（和） | 玉置 卓(京大) / 大舘 陽太(熊本大) / 河村 彰星(九州大学) / 垣村 尚徳(慶應義塾大学) / 泉 泰介(名古屋工業大学) |
| 幹事氏名（英） | Suguru Tamaki(Kyoto Univ.) / Yota Otachi(Kumamoto Univ) / 河村 彰星(九州大学) / 垣村 尚徳(慶應義塾大学) / 泉 泰介(名古屋工業大学) |
| 幹事補佐氏名（和） | 脊戸 和寿(成蹊大) |
| 幹事補佐氏名（英） | Kazuhisa Seto(Seikei Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing / Special Interest Group on Algorithms |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 半順序集合の次元を求める固定パラメータアルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | Parameterized Algorithms for Order Dimension |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 半順序集合 / partially ordered set |
| キーワード(2)（和/英） | 次元 / dimension |
| キーワード(3)（和/英） | 固定パラメータアルゴリズム / fixed-parameter algorithm |
| キーワード(4)（和/英） | 木幅 / treewidth |
| 第 1 著者 氏名（和/英） | 小林 靖明 / Yasuaki Kobayashi |
| 第 1 著者 所属（和/英） | 京都大学(略称：京大) Kyoto University(略称：Kyoto Univ.) |
| 発表年月日 | 2019-05-11 |
| 資料番号 | COMP2019-8 |
| 巻番号（vol） | vol.119 |
| 号番号（no） | COMP-21 |
| ページ範囲 | pp.91-95(COMP), |
| ページ数 | 5 |
| 発行日 | 2019-05-03 (COMP) |