2003年8月のコンピュテーション研究会
★コンピュテーション研究会（COMP）
専門委員長 岩間一雄 副委員長 戸田誠之助
幹事 瀧本英二・牧野和久
日時: 8月1日 (金) 9:30 - 17:30
(一人 20分発表 + 5分質疑の予定）
会場: 広島大学 工学部 A1棟 第二類類会議室 C1-112
〒739-8527 東広島市鏡山1-4-1
Tel: 0824-24-7674
交通: JR山陽新幹線 東広島駅からタクシー15分．
JR山陽本線 西条駅からバス広島大学行き20分 広大東口(工学部前)下車．
東広島キャンパス内の施設配置図については，
http://www.hiroshima-u.ac.jp/add_html/access/ja/saijyo7.html
を御覧下さい．会場はこの図の左端のA1棟とC1棟の境界付近に
あります．
連絡先: 藤田 聡
広島大学大学院 工学研究科 情報工学専攻
Tel & Fax 0824-24-7674
fujita@se.hiroshima-u.ac.jp
=================================================================
＊＊＊チュートリアル講演＊＊＊
演題：「局所情報を用いる有限グラフ上の乱歩のヒッティング時間と
カバー時間」
講師：池田 諭 先生（東京農工大学工学部）
概要：
通常の有限グラフ上の乱歩のヒッティング時間とカバー時間がどの有限
グラフに対しても共に O(n^3) であることはよく知られている．一方，
lollipopと呼ばれるグラフに対して，ヒッティング時間とカバー時間は
共に Ω(n^3) であり，したがって，この評価は最良である．
本講演では, 隣接頂点の次数を利用すれば，ヒッティング時間が
O(n^2)，カバー時間が O(n^2 log n) である遷移規則を見いだすこと
ができることを示す．パスグラフのヒッティング時間はどの遷移規則に
対しても Ω(n^2) であり，隣接頂点の次数はヒッティング時間の最適化
に関しては必要十分な情報である．
=================================================================
議題
9:30 - 10:45
インスタンスの進化に注目したTSPの発見的解法の提案と評価
○梅實 真一郎・藤田 聡（広島大学）
障害物を有する格子スタイナー木問題に対する発見的アルゴリズムAGRF
○藤本 誠・高藤 大介・田岡 智志・渡邉 敏正（広島大学）
橋目 昭彦（松下電工）
最大重みマッチングに基づくグラフのk辺連結化アルゴリズム
○田岡 智志・渡邉 敏正（広島大学）・間島 利也（広島国際大学）
藤原 佑揮（日本ビクター）
11:00 - 12:15
リバウンドチューリング機械に関するある性質
○井上 克司・伊藤 暁・上浦 隆史（山口大学）
ホルガー ピーターセン（シュツットガルト大学）・張 嵐（東芝）
パス限定マルチヘッド有限オートマトン
井上 智史（日立製作所）・○井上 克司・伊藤 暁・王 躍（山口大学）
Optimal Simulation of Dynamically Reconfigurable Row/Column Buses by Statically Fixed Buses
松前 進 (鳥取環境大学)
13:30 - 14:30 【チュートリアル講演】
局所情報を用いる有限グラフ上の乱歩のヒッティング時間とカバー時間
○池田 諭（東京農工大）・久保 泉（広島工業大学）
奥本 哲大（日立製作所）・山下 雅史（九州大学）
14:45 - 16:00
A self-stabilizing token passing in mobile ad hoc networks
木庭 淳（神戸商科大学）
平均乗車時間を最小にする路線バスの運行経路決定方式の提案と評価
〇林 昌紀 ・ 藤田 聡(広島大学)
3以下の局所点連結度要求を持つグラフのコスト付き供給点配置問題
○藤田 等士・石井 利昌・永持 仁（豊橋技術科学大学）
16:15 - 17:30
突然変異のある単調増加数列の割り当てについて
渋沢 進（茨城大学）
流れの中のボロノイ図の近似構成法
○西田 徹志・杉原 厚吉（東京大学）
決定木モデルにおける予測アルゴリズムについて
○須子 統太・野村 亮・松嶋 敏泰・平澤 茂一（早稲田大学）