平成18年度 第1回 全体会議

開催案内

日時 6月21日(水) 15:00 〜 22日(木) 16:00
会場 九州大学 ベンチャービジネスラボラトリ 3階 セミナー室
〒812-8581 福岡市東区箱崎6-10-1
地図: http://www.vbl.kyushu-u.ac.jp/map.html
懇親会 6/21(水) 19:00 〜
工学部食堂
予算 3,500円程度
>> 懇親会参加申込をお願いします。
>> 幹事の方は、 6/22 (木) お昼の 幹事会の参加申込もお願いします。

プログラム

6月21日(水)

15:00-16:00 招待講演: 最小節点ランキング全域木問題について
  増山繁 (豊橋技科大)
16:15-18:45 未解決問題セッション
接尾辞配列の圧縮の下界を得る試みについて
  青野良範, 河内亮周, 河村彰星, 渡辺治 (東工大)
ワイヤレスネットワーク
  徳山豪 (東北大)
オンライン TSP
  宮野英次 (九工大)
19:00- 懇親会

6月22日(木)

9:15-10:15 招待講演: 平面グラフの分枝幅と分枝分割
  玉木久夫 (明治大)
10:30-11:30 招待講演: ε-近似 k-制限最小値独立置換族のサイズの下界
  伊東利哉 (東工大)
11:30-13:15 昼休み
幹事会 (工学部2号館 B401)
13:15-14:45 全体討論
15:00-16:00 招待講演: 情報爆発時代に向けた新しい IT 基盤技術の研究
  喜連川優 (東大)

講演要旨

最小節点ランキング全域木問題について
講演者:増山繁
要旨: 本発表では、まず、最小節点ランキング全域木問題がNP困難であること を示し、次に、区間グラフ、外平面グラフ上での多項式時間アルゴリズムを紹 介する。また、関連した話題にも言及する。
平面グラフの分枝幅と分枝分割
講演者:玉木久夫
要旨: グラフの分枝幅・分枝分割は、木幅・木分割と同種の概念 であり、幅の小さい分枝分割は、グラフ上のさまざまな組み合わせ問題を 効率よく解くために利用することができる。一般のグラフの 最小幅分枝分割を求める問題は木分割の場合と同様にNP困難であるが、 平面グラフに対してはSeymour とThomas による多項式時間の アルゴリズムが知られている。この講演では彼らのアルゴリズムについて解説し、 それを改良しようとする講演者らの努力と結果について述べる。
共同研究者:Qianping Gu, 吉武由実
ε-近似 k-制限最小値独立置換族のサイズの下界
講演者:伊東利哉
要旨: 最小値独立置換族(とその拡張概念であるε-近似 k-制限最小値 独立置換族)は,インターネット上に存在する多数の類似した文書の特定に有用 であることが知られており,それらの構成法,置換族のサイズに関する(非)構成的 上界・下界が数多く示されている.本論文では,まず始めに完全グラフの多色 枝塗りに関するラムゼー数の上界を評価し,さらに代数的手法を用いることで, より厳密なε-近似 k-制限最小値独立置換族${\cal F} \subseteq S_{n}$ のサイズの下界を導出する.
共同研究者:永谷達也