No.1799

2012/01/30〜2012/02/01

平田　富夫

Tomio Hirata

目　次

1. 完全マッチング数え上げの高速な指数時間アルゴリズムについて (アルゴリズムと計算理論の新展開)---------------------------------------1

　　　　名古屋工業大学大学院情報科学研究科 / 名古屋工業大学大学院情報科学研究科　　　泉 泰介 / 和田山 正　(Izumi,Taisuke / Wadayama,Tadashi)

　

2. 多数決3分木への理論式分解 (アルゴリズムと計算理論の新展開)-----------------------------------------------------------------------13

　　　　京都大学次世代研究者育成センター (白眉プロジェクト)　　　上野 賢哉　(Ueno,Kenya)

　

3. Hybrid Automata Theoretic Specification and Verification of CPU-DRP Reconfigurable Systems (New Trends in Algorithms and Theory of Computation)---21

　　　　金沢大学自然科学研究科 / 金沢大学自然科学研究科 / 金沢大学自然科学研究科 / 金沢大学理工研究域　　　柳瀬 龍 / 高 穎 / 南 翔太 / 山根 智　(Yanase,Ryo / Gao,Ying / Minami,Shota / Yamane,Satoshi)

　

4. 抽象化洗練を用いた時間確率システムに対する形式的検証手法 (アルゴリズムと計算理論の新展開)----------------------------------------29

　　　　金沢大学大学院自然科学研究科 / 金沢大学大学院自然科学研究科 / 金沢大学理工研究域電子情報学系　　　清水 隆也 / 森下 篤 / 山根 智　(Shimizu,Takaya / Morimoto,Atsushi / Yamane,Satoshi)

　

5. セルオートマトンの合成とリミットサイクルについて (アルゴリズムと計算理論の新展開)------------------------------------------------37

　　　　九州産業大学基礎教育センター / 九州大学大学院数理学研究院　　　石田 俊一 / 井口 修一　(Ishida,Toshikazu / Inokuchi,Shuichi)

　

6. 合同な四角形による球面タイリングの分類 (アルゴリズムと計算理論の新展開)----------------------------------------------------------44

　　　　東北大学大学院理学研究科数学専攻 / 国際協力機構 / 東北大学理学研究科化学専攻　　　赤間 陽二 / 坂野 雄大 / 中村 公亮　(Akama,Yohji / Sakano,Yudai / Nakamura,Kosuke)

　

7. Variants of Petri net controlled grammars and their parsing algorithms (New Trends in Algorithms and Theory of Computation)------49

　　　　富山県立大学　　　西田 泰伸　(Nishida,Taishin Yasunobu)

　

8. Relations between language classes in terms of insertion and locality (New Trends in Algorithms and Theory of Computation)-------57

　　　　九州大学研究戦略企画室　　　藤岡 薫　(Fujioka,Kaoru)

　

9. 海草全単射の漸減構築 (アルゴリズムと計算理論の新展開)----------------------------------------------------------------------------60

　　　　東北大学大学院農学研究科　　　酒井 義文　(Sakai,Yoshifumi)

　

10. アスペクト比を固定した最小の周囲長方形について (アルゴリズムと計算理論の新展開)-------------------------------------------------65

　　　　埼玉大学工学部 / 埼玉大学理工学研究科　　　小林 有 / 堀山 貴史　(Kobayashi,Tamotsu / Horiyama,Takashi)

　

11. 滑らかな常微分方程式の計算量 (アルゴリズムと計算理論の新展開)-------------------------------------------------------------------67

　　　　東京大学情報理工学系研究科 / 東京大学情報理工学系研究科 / ダルムシュタット工科大学 / ダルムシュタット工科大学　　　太田 浩行 / 河村 彰星 / ツィーグラー・マルチン / レースニク・カルステン　(Ota,Hiroyuki / Kawamura,Akitoshi / Ziegler,Martin / Rosnick,Carsten)

　

12. On QMA Protocols with Two Short Quantum Proofs (New Trends in Algorithms and Theory of Computation)-----------------------------73

　　　　東京大学情報理工学系研究科 / 大阪府立大学理学系研究科 / 大阪府立大学理学系研究科　　　Le Gall Francois / 中川 翔太 / 西村 治道　(Le Gall,Francois / Nakagawa,Shota / Nishimura,Harumichi)

　

13. Limiting Negations in Probabilistic Circuits (New Trends in Algorithms and Theory of Computation)------------------------------81

　　　　島根大学総合理工学研究域　　　森住 大樹　(Morizumi,Hiroki)

　

14. Greedy Algorithms for Multi-Queue Buffer Management with Class Segregation (New Trends in Algorithms and Theory of Computation)---84

　　　　東京工業大学像情報工学研究所 / 東京工業大学情報理工学研究科　　　伊東 利哉 / 吉本 聖司　(ITOH,TOSHIYA / YOSHIMOTO,SEIJI)

　

15. 格子グラフ上の最短経路問題のための劣線形領域アルゴリズム (アルゴリズムと計算理論の新展開)---------------------------------------92

　　　　東京工業大学大学院情報理工学研究科数理計算科学専攻 / 東京工業大学理学部情報科学科 / 東京工業大学理学部情報科学科　　　今井 達也 / 野口 俊輔 / 藤 哲郎　(Imai,Tatsuya / Noguchi,Shunsuke / Fuji,Tetsuro)

　

16. GPU を用いた簡潔 trie の並列探索 (アルゴリズムと計算理論の新展開)--------------------------------------------------------------100

　　　　JST ERATO湊離散構造処理系プロジェクト / 東京工業大学情報理工学研究科　　　田部井 靖生 / 田中 秀宗　(Tabei,Yasuo / Tanaka,Hidetoki)

　

17. Probabilistic Stabilization under Probabilistic Schedulers (New Trends in Algorithms and Theory of Computation)----------------103

　　　　九州大学システム情報科学研究院 / Paris 6 / 九州大学システム情報科学研究院　　　山内 由紀子 / Tixeuil Sebastien / 山下 雅史　(Yamauchi,Yukiko / Tixeuil,Sebastien / Yamashita,Masafumi)

　

18. ラベル選択付最小連結全域部分グラフ問題と化学構造式OCRへの応用 (アルゴリズムと計算理論の新展開)---------------------------------111

　　　　茨城大学工学部情報工学科 / 九州大学大学院数理学研究院　　　藤芳 明生 / 鈴木 昌和　(Fujiyoshi,Akio / Suzuki,Masakazu )

　

19. 8次格子モデルによる表の行/列操作 (アルゴリズムと計算理論の新展開)--------------------------------------------------------------118

　　　　日本大学文理学部 / 電気通信大学情報理工学研究科 / 東洋大学工業技術研究所 / 電気通信大学情報理工学研究科 / 日本大学文理学部　　　高加 晋司 / 後藤 隆彰 / 土田 賢省 / 西野 哲朗 / 夜久 竹夫　(Koka,Shinji / Goto,Takaaki / Tsuchida,Kensei / Nishino,Tetsuro / Yaku,Takeo)

　

20. On the base-line location problem for the maximum weight region decomposable into base-monotone shapes (New Trends in Algorithms and Theory of Computation)---123

　　　　埼玉大学理工学研究科 / 東北大学情報科学研究科 / 九州大学経済学研究院 / 東北大学情報科学研究科 / 北陸先端科学技術大学院大学情報科学研究科 / 情報学研究所　　　堀山 貴史 / 伊藤 健洋 / 小野 廣隆 / 大舘 陽太 / 上原 隆平 / 宇野 毅明　(Horiyama,Takashi / Ito,Takehiro / Ono,Hirotaka / Otachi,Yota / Uehara,Ryuhei / Uno,Takeaki)

　

21. ランダムグラフ上の多種ランダムウォークの全訪問時間 (アルゴリズムと計算理論の新展開)--------------------------------------------130

　　　　九州大学システム情報科学府情報学専攻 / 九州大学システム情報科学研究院情報学部門 / 九州大学システム情報科学研究院情報学部門 / 九州大学経済学研究院 / 九州大学システム情報科学研究院情報学部門　　　穂坂 祐輔 / 山内 由紀子 / 来嶋 秀治 / 小野 廣隆 / 山下 雅史　(Hosaka,Yusuke / Yamauchi,Yukiko / Kijima,Shuji / Ono,Hirotaka / Yamashita,Masafumi)

　

22. Approximating Steiner Tree and Tree Cover problems in Directed Graphs (New Trends in Algorithms and Theory of Computation)-----137

　　　　豊橋技術科学大学大学院工学研究科情報・知能工学専攻 / 豊橋技術科学大学大学院工学研究科情報・知能工学専攻　　　日比 智也 / 藤戸 敏弘　(Hibi,Tomoya / Fujito,Toshihiro)

　

23. グラフの正方格子上への単位長配置について (アルゴリズムと計算理論の新展開)------------------------------------------------------145

　　　　群馬大学大学院工学研究科情報工学専攻 / 群馬大学大学院工学研究科情報工学専攻　　　高田 健司 / 天野 一幸　(Takada,Kenji / Amano,Kazuyuki)

　

24. Heuristic Algorithms for Rectilinear Block Packing (New Trends in Algorithms and Theory of Computation)------------------------153

　　　　名古屋大学情報科学研究科 / 名古屋大学情報科学研究科 / 名古屋大学工学研究科 / 名古屋大学情報科学研究科　　　Hu Yannan / 橋本 英樹 / 今堀 慎治 / 柳浦 睦憲　(Hu,Yannan / Hashimoto,Hideki / Imahori,Shinji / Yagiura,Mutsunori)

　

25. グラフの頂点価格付け問題に対する実用的近似解法 (アルゴリズムと計算理論の新展開)------------------------------------------------157

　　　　東北大学情報科学研究科 / 東北大学情報科学研究科　　　中村 坂紀 / 塩浦 昭義　(Nakamura,Sakaki / Shioura,Akiyoshi)

　

26. ストリーム中の頻出アイテム発見に対するO(loglog$N$)領域乱択アルゴリズム (アルゴリズムと計算理論の新展開)------------------------159

　　　　九州大学システム情報科学研究院 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院　　　緒方 正虎 / 山内 由紀子 / 来嶋 秀治 / 山下 雅史　(Ogata,Masatora / Yamauchi,Yukiko / Kijima,Shuji / Yamashita,Masafumi)

　

27. 距離遺伝2部グラフ上のハミルトン閉路アルゴリズム (アルゴリズムと計算理論の新展開)-----------------------------------------------163

　　　　名古屋大学大学院情報科学研究科 / 名古屋大学大学院情報科学研究科　　　高須賀 将秀 / 平田 富夫　(Takasuka,Masahide / Hirata,Tomio)

　

28. 記憶付き可逆論理素子の能力の階層構造について (アルゴリズムと計算理論の新展開)--------------------------------------------------167

　　　　広島大学大学院工学研究科 / 広島大学大学院工学研究科　　　向井 優太 / 森田 憲一　(Mukai,Yuuta / Morita,Kenichi)

　

29. mm-GNAT における分割点集合の選択手法に関する研究 (アルゴリズムと計算理論の新展開)----------------------------------------------171

　　　　東海大学大学院理学研究科 / 東海大学理学部　　　謝 評芳 / 大西 建輔　(Xie,Pingfang / Onishi,Kensuke)

　

30. Automata inspired by biochemical reaction (New Trends in Algorithms and Theory of Computation)---------------------------------179

　　　　早稲田大学大学院教育学研究科 / 電気通信大学大学院電気通信学研究科 / 早稲田大学教育・総合科学学術院　　　大久保 文哉 / 小林 聡 / 横森 貴　(Okubo,Fumiya / Kobayashi,Satoshi / Yokomori,Takashi)

　

31. トリックテイキングゲームの計算量と必勝戦略 (アルゴリズムと計算理論の新展開)----------------------------------------------------183

　　　　電気通信大学大学院情報理工学研究科情報・通信工学専攻 / 電子通信大学大学院情報理工学研究科情報・通信工学専攻　　　中井 健一朗 / 武永 康彦　(Nakai,Kenichiro / Takenaga,Yasuhiko)

　

32. 連結文字列の圧縮長について (アルゴリズムと計算理論の新展開)--------------------------------------------------------------------187

　　　　東京工業大学大学院情報理工学研究科　　　遊佐 俊彦　(Yusa,Toshihiko)

　

33. 単位円交差グラフの線形構造を持つ部分クラスについて (アルゴリズムと計算理論の新展開)--------------------------------------------191

　　　　群馬大学工学研究科 / 群馬大学工学研究科 / 群馬大学工学研究科 / 群馬大学工学研究科 / 群馬大学工学研究科 / 群馬大学工学研究科　　　林 貴史 / 木野 徹 / 桑原 勇人 / 長澤 亮介 / 芝田 悠華 / 山崎 浩一　(Hayashi,Takashi / Kino,Toru / Kuwabara,Yuto / Nagasawa,Ryosuke / Shibata,Yuka / Yamazaki,Koichi)

　

34. Pattern Formation by Fully Asynchronous Mobile Robots (New Trends in Algorithms and Theory of Computation)---------------------195

　　　　九州大学システム情報科学研究院 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院　　　藤永 直 / 山内 由紀子 / 来嶋 秀治 / 山下 雅史　(Fujinaga,Nao / Yamauchi,Yukiko / Kijima,Shuji / Yamashita,Masafumi)