平成18年度 第１回 全体会議
開催案内
| 日時 | 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}$
のサイズの下界を導出する．
共同研究者：永谷達也