| 講演抄録／キーワード |
| 講演名 |
2006-04-26 15:45
コーダルグラフに関する同型性判定のための単純なアルゴリズム
○戸田誠之助（日大） |
| 抄録 |
（和） |
まず、本稿で示しているアルゴリズムは根本的に間違えており、発表時点で訂正できていないことを述べておきたい。以下、本研究の問題の背景だけを述べる。筆者による以前の研究[IEICE Technical Report, COMP2005-24; IEICE Transactions on Information and Systems, August 2006に掲載予定]において、コーダルグラフの自己同型群を求めるためのアルゴリズムを設計し、それを利用することによって同型性も判定できることを示した。しかし、そこでは群論的手法を多用しており、複雑で時間量の解析も困難であった。さらに、自己同型群のもとで不変な木表現（s-木）が構成可能であるといった事実以外には、コーダルグラフに関する様々な性質をまったく利用していないものになっていた（注：これは群論的手法を多用しているためである）。そこで、コーダルグラフの性質をうまく利用することによって、より単純なアルゴリズムを設計できるのではないかということが素直な疑問として残されていた。本研究では、この疑問をいったんは解決できたと考えたが、上述したように残念ながら間違えていた。この疑問にいま少し取り組み、正しいアルゴリズムが設計できたときには、再度発表したいと考えている。 |
| （英） |
(Not available yet) |
| キーワード |
（和） |
同型性判定問題 / コーダルグラフ / 木表現 / アルゴリズム / 計算量理論 / / / |
| （英） |
/ / / / / / / |
| 文献情報 |
信学技報, vol. 106, no. 29, COMP2006-8, pp. 57-62, 2006年4月. |
| 資料番号 |
COMP2006-8 |
| 発行日 |
2006-04-19 (COMP) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|
| 研究会情報 |
| 研究会 |
COMP |
| 開催期間 |
2006-04-26 - 2006-04-26 |
| 開催地（和） |
京都大学 |
| 開催地（英） |
Kyoto University |
| テーマ（和） |
一般 |
| テーマ（英） |
|
| 講演論文情報の詳細 |
| 申込み研究会 |
COMP |
| 会議コード |
2006-04-COMP |
| 本文の言語 |
日本語 |
| タイトル（和） |
コーダルグラフに関する同型性判定のための単純なアルゴリズム |
| サブタイトル（和） |
|
| タイトル（英） |
A simple algorithm for testing isomorphism of chordal graphs |
| サブタイトル（英） |
|
| キーワード(1)（和/英） |
同型性判定問題 / |
| キーワード(2)（和/英） |
コーダルグラフ / |
| キーワード(3)（和/英） |
木表現 / |
| キーワード(4)（和/英） |
アルゴリズム / |
| キーワード(5)（和/英） |
計算量理論 / |
| キーワード(6)（和/英） |
/ |
| キーワード(7)（和/英） |
/ |
| キーワード(8)（和/英） |
/ |
| 第1著者 氏名（和/英/ヨミ） |
戸田 誠之助 / Seinosuke Toda / トダ セイノスケ |
| 第1著者 所属（和/英） |
日本大学 (略称： 日大)
Nihon University (略称： Nihon Univ.) |
| 第2著者 氏名（和/英/ヨミ） |
/ / |
| 第2著者 所属（和/英） |
(略称： )
(略称： ) |
| 第3著者 氏名（和/英/ヨミ） |
/ / |
| 第3著者 所属（和/英） |
(略称： )
(略称： ) |
| 第4著者 氏名（和/英/ヨミ） |
/ / |
| 第4著者 所属（和/英） |
(略称： )
(略称： ) |
| 第5著者 氏名（和/英/ヨミ） |
/ / |
| 第5著者 所属（和/英） |
(略称： )
(略称： ) |
| 第6著者 氏名（和/英/ヨミ） |
/ / |
| 第6著者 所属（和/英） |
(略称： )
(略称： ) |
| 第7著者 氏名（和/英/ヨミ） |
/ / |
| 第7著者 所属（和/英） |
(略称： )
(略称： ) |
| 第8著者 氏名（和/英/ヨミ） |
/ / |
| 第8著者 所属（和/英） |
(略称： )
(略称： ) |
| 第9著者 氏名（和/英/ヨミ） |
/ / |
| 第9著者 所属（和/英） |
(略称： )
(略称： ) |
| 第10著者 氏名（和/英/ヨミ） |
/ / |
| 第10著者 所属（和/英） |
(略称： )
(略称： ) |
| 第11著者 氏名（和/英/ヨミ） |
/ / |
| 第11著者 所属（和/英） |
(略称： )
(略称： ) |
| 第12著者 氏名（和/英/ヨミ） |
/ / |
| 第12著者 所属（和/英） |
(略称： )
(略称： ) |
| 第13著者 氏名（和/英/ヨミ） |
/ / |
| 第13著者 所属（和/英） |
(略称： )
(略称： ) |
| 第14著者 氏名（和/英/ヨミ） |
/ / |
| 第14著者 所属（和/英） |
(略称： )
(略称： ) |
| 第15著者 氏名（和/英/ヨミ） |
/ / |
| 第15著者 所属（和/英） |
(略称： )
(略称： ) |
| 第16著者 氏名（和/英/ヨミ） |
/ / |
| 第16著者 所属（和/英） |
(略称： )
(略称： ) |
| 第17著者 氏名（和/英/ヨミ） |
/ / |
| 第17著者 所属（和/英） |
(略称： )
(略称： ) |
| 第18著者 氏名（和/英/ヨミ） |
/ / |
| 第18著者 所属（和/英） |
(略称： )
(略称： ) |
| 第19著者 氏名（和/英/ヨミ） |
/ / |
| 第19著者 所属（和/英） |
(略称： )
(略称： ) |
| 第20著者 氏名（和/英/ヨミ） |
/ / |
| 第20著者 所属（和/英） |
(略称： )
(略称： ) |
| 講演者 |
第1著者 |
| 発表日時 |
2006-04-26 15:45:00 |
| 発表時間 |
35分 |
| 申込先研究会 |
COMP |
| 資料番号 |
COMP2006-8 |
| 巻番号（vol） |
vol.106 |
| 号番号（no） |
no.29 |
| ページ範囲 |
pp.57-62 |
| ページ数 |
6 |
| 発行日 |
2006-04-19 (COMP) |
|