ミニ研究集会 (グラフアルゴリズム)
Chordal graphに関する計算問題ならびにアルゴリズムを中心に、
研究成果の発表と新たな課題探求に向けた討論を行った．詳細は
次の通り．
- 日時：
- 3月19日(土) 午前10時〜午後6時
- 場所：
- 日本大学文理学部8号館レクチャーホール
- 参加者数：
- 19名
- 研究発表：
- (1) 10:00〜11:20，Computing automorphism groups of chordal graphs whose
simplicial components are of small size，戸田誠之助（日大文理）
-
（概要）
小さなサイズの単体成分へと分解可能な任意のchordal graphに対して、
その自己同型群が多項式時間計算可能であることを示した．
- (2) 11:30〜12:30，2-リンクパズルの多項式時間解法，牧野 格三（東工大）
-
（概要）ナンバーリンクパズルを「k-リンクパズル」と呼ばれるグラフ論的な
計算問題へと一般化し，3×(偶数)や4×(偶数)といった格子グラフに関する
2-リンクパズルに対して多項式時間アルゴリズムを示すとともに，一般の格子
グラフに関する予想を述べた．さらに，参加者を交えた討論を経て新たな研究
課題が見出された．
- (3) 13:30〜15:00，On the Laminar Structure of Ptolemaic and
Distance Hereditary Graphs，上原 隆平(JAIST)，宇野裕之(大阪府立大学)
-
（概要）
Chordal graph（のクラス）とdistance hereditary graph（のクラス）の
共通部分として特徴付けられている Ptolemaic graph（のクラス）に対して，
ある種の木表現モデルが存在すること，その木表現モデルが各Ptolemaic graph
に対して一意的に定まること，ならびに，その木表現モデルを線形時間で構築
できることを示した．さらに，この結果をもとに，Ptolemaic graph（のクラス）
に対する認識問題や同型性判定問題が線形時間計算可能であることを示した．
また，この研究の発展的可能性として，distance hereditary graphに対する
同様の木表現モデルの存在性に関する予想を述べた．
- (4) 15:15〜16:45，On precoloring extension problem，名古屋孝幸（東京電機大学）
-
（概要）グラフの precoloring extension problem (PREXTと略す)に対して，
一般のグラフに対してはNP完全であることや，クリーク数を制限したchordal
graphに対して多項式時間計算可能であることを紹介した．また，PREXTを
制限した1-PREXT問題に対して，chordal graphに対するネットワークフロー
を用いた多項式時間アルゴリズムを紹介した．
研究発表終了後，午後6時頃まで討論を行った．討論の間に，グラフ自己同型群
問題の応用研究として，河内亮周氏（東工大）に次の成果を発表して頂いた．
- (5) Computational Distinguishability between Quantum States and Its
Applications，A. Kawachi, T. Koshiba, H. Nishimura and T. Yamakami
-
（概要）確率分布に対する判別問題の自然な一般化として，二つの量子状態を
判別する問題（QSCDff）を新たに定義し，その問題が落とし戸関数の性質を
有すること，その最悪計算量と平均計算量が等価であること，さらに，
その最悪計算量がグラフ自己同型群問題の最悪計算量と同等以上であること
を示した．
各地から多くの参加者を得て活発な討論が行われ，発展的研究課題を見出すことも
できて，とても充実した研究集会であった．
