ISSN 1880-2818

数理解析研究所講究録 1894

計算理論とアルゴリズムの新潮流

京都大学数理解析研究所
2014 年 5 月

数理解析研究所講究録は，京都大学数理解析研究所の共同利用研究集会および共同研究の記録として 1964 年に刊行が開始されました．現在の共同利用共同研究拠点(2010 年発足) の前身である，全国共同利用研究所として当研究所が発足した翌年のことでしたが以来半世紀，毎年数十巻を刊行し，2012 年には第 1800 巻が刊行されるに至りました．第 1 巻から第 1840 巻までに収録された論文数は 26,808 編，総頁数は 317,199 頁という膨大なものであり，最先端の数学数理科学分野の研究状況を伝えるのみならず，我が国の数学数理科学の発展の歴史を留める文献として，他に類例を見ない論文集となっています．

講究録の内容は当研究所のウェブサイトおよび京都大学の学術情報リポジトリにおいても公開され，年間の総アクセス数は 1254383 回 (2012 年度) を数えるなど多数の方にご利用いただいています．

講究録の使用言語は論文著者の判断に任されていますが，結果的に日本語が多用されていることが特徴の一つとなっています．その結果，講究録は，数学数理科学の広い領域における最先端の専門知識に母国語でアクセスできるものとして，近年の英語化の流れの中で，重要な文献となりつつあります．

当研究所の共同利用事業に参加し講究録の論文を執筆していただいた多数の方々に対し，講究録を大きく成長させていただいたことを深く感謝いたしますとともに，これからも，当研究所の共同利用共同研究拠点としての活動にご参加いただき，講究録の発展にご協力いただけますよう心よりお願い申し上げます．

RIMS$K\hat{o}k\gamma\hat{u}roku$

1894

New Streams of Computation Theory and Algorithms
January$28\sim 30_{y}$2014edited by Masayuki Takeda

May, 2014

Research Institute for Mathematical Sciences
Kyoto University, Kyoto, Japan
This is a report of research done at the Research Institute for MathematicalSciences, Kyoto University. The papers contained herein are in final form
and will not be submitted for publication elsewhere.

計算理論とアルゴリズムの新潮流
New Streams of Computation Theory and Algorithms
RIMS 研究集会報告集
2014 年 1 月 28 日
月 30 日研究代表者
竹田 正幸 (Masayuki Takeda)$\sim 1$目次

1. フーリエ変換による置換族の独立性解析 $————————————————-1$
長岡技科大 (Nagaoka U. Tech.)鈴木 孝 (Takashi Suzuki)
Nguyen Thai Phat
武井 由智 (Yoshinori Takei)’/’/

2. フーリエ変換によるあみだくじの解析

10$————-$

長岡技科大 (Nagaoka U. Tech.)

中村武井’/

彰吾 (Shogo Nakamura)
由智 (Yoshinori Takei)

3. Propositional Logic and Cellular Automata $—————————————-19$

4.

$A$

九大数理学 (Kyushu $U$ .)井口
九産大基礎教育センター (Kyushu Sangyo $U$ .)修一 (Shuichi Inokuchi)

石田俊一 (Toshikazu Ishida)

河原康雄 (Yasuo Kawahara)$————————$

note on picture insertion systems
福岡女子大国際文理 (Fukuoka Women’s $U$ .)藤岡

5. 無限グラフに対する結婚定理と逆数学
東北大理学 (Tohoku$U$

薫 (Kaoru Fujioka)

—-)

藤原

6. グラフの経路固定サーバ割当問題に関する研究
東北大情報科学 (Tohoku $U$ .)$——–$大日野伊藤鈴木内澤周〃〃

山形大理工学 (Yamagata $U$ .)東北大情報科学 (Tohoku $U$ .)$- i -$

誠 (Makoto Fujiwara)

肇 (Hajime Oohino)

健洋 (Takehiro Ito)
顕 (Akira Suzuki)
啓 (Kei Uchizawa)
暁 (Xiao Zhou)

32

7. 境界上の重みの釣合せ $—————————————————————–45$
Luis Barba

Free U. Brussels/Carleton U.
KAISTCarleton U.
POSTECH
Fudan . /GUtech

鄭地園 (Otfried Cheong)
Jean-Lou De Carufel

Michael Dobbins
Rudolf Fleischer$U$

東大情報理工学系 (U. Tokyo)
国立情報学研 (NII)
電通大情報理工学 (UEC)
EPFL/Alff\’ed R\’enyi Inst. Math.

Fudan

$U$

河村

岡本 吉央 (Yoshio Okamoto)
J\’anos Pach
唐淵 (Yuan Tang)
徳山 豪 (Takeshi Tokuyama).

東北大情報科学 (Tohoku $U$ .)Carleton U.

Fudan

$U$

Sander Verdonschot
王 天豪 (Tianhao Wang).

8. パリティハミルトン閉路問題$—$

九大システム情報科学 (Kyushu’/彰星 (Akitoshi Kawamura)

Matias Korman

$U$.)

’/
’/

9. 最適選好マッチングの端点集合の構造について
九大システム情報科学 (Kyushu $U$ .)

西山
山内
来嶋
山下

$————————————–58$
平川

山内
来嶋
山下’/

’/
’/

宏 (Hiroshi Nishiyama)
由紀子 (Yukiko Yamauchi)
秀治 (Shuji Kijima)
雅史 (Masafumi Yamashita)

瑞樹 (Mizuki Hirakawa)
由紀子 (Yukiko Yamauchi)
秀治 (Shuji Kijima)
雅史 (Masafumi Yamashita)

10. 全域木混雑度問題に対する $LP$ 緩和について $——————————————-63$
九大・システム情報科学 (Kyushu $U$ .)’/’/’/

久保
山内
来嶋
山下

浩平 (Kohei Kubo)
由紀子 (Yukiko Yamauchi)
秀治 (Shuji Kijima)
雅史 (Masafumi Yamashita)

11. 移動ビザンチン合意アルゴリズムのための高信頼性伝送アルゴリズム $——–67$
九大・システム情報科学．(Kyushu$U$.)〃〃$- 11 -$

佐々木 徹 (Toru Sasaki)
山内 由紀子 (Yukiko Yamauchi)
来嶋 秀治 (Shuji Kijima)
山下 雅史 (Masafumi Yamashita)12. 距離遺伝グラフのハミルトン閉路を見つける線形時間アルゴリズム
名大情報科学 (Nagoya$U$.)

神保
平田’/

孝則 (Takanori Jimbo)
富夫 (Tomio Hirata)

13. 多人数不完全情報ゲームに対する局面評価値を用いたモンテカルロ法
中央大理工学 (Chuo$U$.)

漆畑$———75$$——–84$

雅士 (Masashi Urushibata)14. モンテカルロ法を用いたボードゲームの対戦プログラム
双対グラフ上の高速プレイアウト手法の提案
神野
中央大理工学 (Chuo $U$ .)––$-\ddot{\dot{m}}-$–89
雅俊 (Masatoshi Jinno)

講究録$K\hat{D}br\hat{u}roku$$RmIS$

K\^oky\^uroku was started in 1964 as the proceedings of symposia, colloquia andworkshops supported by $RT$$MS$ , the ReseaIch Institute for Mathematical Sciences, Kyoto-University It was the next year of the establishment of RIMS as one of the nationwide

perative Research Centers, the $pre\infty ding$ system of the current Joint UsagelRese 下 arch$C\infty$Centers that started in 2010. For half a century since then, about 50 to 60 volumes have been
issued each year, and the 1, $800th$ volume was issued in 2012. The volumes offromthe lst through the 1, $840th$, containing enormous 26,808 articles and 317,199 pages, not only
deliver the latest research activities in mathematics and mathematical sciences but also
constitute valuable and incomparable collections of articles that pass down history of progressof mathematics and mathematical science in Japan$K\hat{0}br\hat{u}\iota oku$

Articles inare available on the websites of RIMS and Kyoto University ResearchInformation Repository They are very frequently accessed on the internet, with a total of as
many as 1,254,383 accesses in 2012.
$K\hat{o}ky\hat{u}\iota oku$

The authors choose the languages to write articles, and many are written in Japanese, which

is one of the characteristics of K\^oky\^uroku. As a result, K6ky\^uroku is regarded as a significant
and important literature which allows easy access to the latest specialized knowledge in thelarge fields of mathematics and mathematical scienoes written in native language $fOr$ Japanesereaders, while more and more research papers are being written in English in recent years.

We are deeply grateful to many of those who have participated in cooperative research
activities of RJMS and greatly developed. We heartily ask $fOr$ your ntinuous$K\hat{o}b\hat{u}rku$$\infty$activities at $RBqS$ as a Joint Usage Research Center and your warm
support and cooperation $f0r$ the fruitful development

participation in$\infty sea\iota ch$$ofK\hat{o}br\hat{u}\iota \mathfrak{v}ku.$