| 講演名 | 2007-05-25 行列集合の自己同型群を求めるための動的計画アルゴリズム 戸田 誠之助, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | X=(U_1∪U_2∪・・・∪U_m∪V,E)を適当なm+1部グラフとする.ただし,U_iとU_jの間には辺は存在しないものとする.その一方で,各辺は適当な全順序集合の要素をラベルとして持ってもよいとする.本稿では,各部集合U_iおよびVを(集合として)固定し,かつ,各辺のラべルを保存するようなXの自己同型群を求める問題を考える.この問題は一般にGl-完全である.従って,現状では,この問題に対して多項式時間アルゴリズムを設計することはとても困難か,あるいは不可能であるとさえ予想される.しかし,各U_iのサイズがある定数以下の場合には(注:Vのサイズは制限しない),多項式時間アルゴリズムが知られている.しかしながら,そのアルゴリズムはcellular algebraと表現論の結果に基づいており,その分,とても込み入ったものになっている.そのため,より単純なアルゴリズムを設計できるか否かが素朴な疑問として生じる.この疑問に関して,本稿では,動的計画法に基づく単純なアルゴリズムを示す. |
| 抄録(英) | Let X=(U_1∪U_2∪・・・∪U_m∪V,E) be an m+1-partite graph such that no edge exists between U_i and U_j for any iI,j. On the other hand, we allow any edge to have a label chosen from any linearly ordered set. In this report, we consider the problem of computing the aumorphism group of X that stabilizes each of partite sets Ui and V and that preserves the labels of all edges. The problem is GI-complete in general and hence it seems very difficult (at least at this moment) to design a polynomial time algorithm for the problem, Thus we consider the restricted case that the size of each U_i except V is bounded above by a constant. For the case, a polynomial time algorithm has been known already. However, the algorithm is very complecated since in particular it depends on several deep results on the theory of cellular algebra and the representation theory of groups. In this report, we demonstrate that we can design a simpler algorithm based on dynamic programming technique but not dependent on those results mentioned above. |
| キーワード(和) | グラフ / 自己同型 / 行列 / 動的計画法 / アルゴリズム / 置換群 |
| キーワード(英) | graph / automorphism / matrix / dynamic programming / algorithm / permutation group |
| 資料番号 | COMP2007-16 |
| 発行日 |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2007/5/18(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Theoretical Foundations of Computing (COMP) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 行列集合の自己同型群を求めるための動的計画アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | A dynamic programmming algorithm for computing automorphism groups of a given set of matrices |
| サブタイトル（和） | |
| キーワード(1)（和/英） | グラフ / graph |
| キーワード(2)（和/英） | 自己同型 / automorphism |
| キーワード(3)（和/英） | 行列 / matrix |
| キーワード(4)（和/英） | 動的計画法 / dynamic programming |
| キーワード(5)（和/英） | アルゴリズム / algorithm |
| キーワード(6)（和/英） | 置換群 / permutation group |
| 第 1 著者 氏名（和/英） | 戸田 誠之助 / Seinosuke TODA |
| 第 1 著者 所属（和/英） | 日本大学文理学部情報システム解析学科 Dept. of Computer Science and System Analysis College of Humanities and Sciences, Nihon University |
| 発表年月日 | 2007-05-25 |
| 資料番号 | COMP2007-16 |
| 巻番号（vol） | vol.107 |
| 号番号（no） | 73 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |