12月20日(金) 一日目(開場9:00) 09:25 - |
12月20日(金) 午前 09:30 - 11:50 |
(1) |
09:30-09:55 |
Reflections on a CFL decision problem "L(G)=Σ* ?" |
○Eiiichi Tanaka |
(2) |
09:55-10:20 |
Algorithms for Independent Set Reconfiguration Problem on Graphs |
Erik D. Demaine・Martin L. Demaine(Massachusetts Inst. of Tech.)・Takehiro Ito(Tohoku Univ.)・Hirotaka Ono(Kyushu Univ.)・○Ryuhei Uehara(JAIST) |
(3) |
10:20-10:45 |
On Enumerating All Maximal Cliques in Unit Disk Graphs |
○Daisuke Suzuki・Taisuke Izumi(Nagoya Inst. of Tech.) |
|
10:45-11:00 |
休憩 ( 15分 ) |
(4) |
11:00-11:25 |
Localization of eigenvector centrality on single-defect networks |
○Hiroki Yamaguchi(Tokyo Inst. of Tech.) |
(5) |
11:25-11:50 |
An empirical study for independent distance dominating sets in large-scale graphs |
○Hiroshi Kadowaki・Liang Zhao(Kyoto Univ.)・Dorothea Wagner(Karlsruhe Inst. of Tech.) |
|
11:50-13:20 |
休憩 ( 90分 ) |
12月20日(金) 午後 13:20 - 16:50 |
(6) |
13:20-13:45 |
プロジェクト閉鎖付き順次独裁メカニズムの拡張に関する研究 |
○神山直之(九大) |
(7) |
13:45-14:10 |
ナップザック問題に対するアルゴリズムを用いた電力割当制御システム |
○森本尚之・藤田 有・吉田雅昭・吉水宏幸・滝山田昌文・明比輝一・田中真実(エネゲート) |
|
14:10-14:25 |
休憩 ( 15分 ) |
(8) |
14:25-14:50 |
The Hidden K-matrix Linear Complementarity Problem is at Least as Hard as Linear Programming over Cubes |
○Jan Foniok(Univ. of Warwick)・Komei Fukuda(ETH Zurich)・Lorenz Klaus(NII/JST) |
(9) |
14:50-15:15 |
Sensitivity, Block Sensitivity, and Certificate Complexity of Unate Functions and Read-Once Functions |
○Hiroki Morizumi(Shimane Univ.) |
|
15:15-15:30 |
休憩 ( 15分 ) |
(10) |
15:30-16:50 |
[チュートリアル講演]計算複雑さへの招待(5):回路から迫るP vs. NP |
○脊戸和寿(成蹊大) |
12月21日(土) 二日目(開場9:00) 09:25 - 16:50 |
12月21日(土) 午前 09:30 - 11:50 |
(11) |
09:30-09:55 |
単純多角形内部の最短経路発見のためのメモリ調節可能アルゴリズム |
○小長谷松雄・浅野哲夫(北陸先端大)・Otfried Cheong(KAIST)・Sang Won Bae(Kyonggi Univ.) |
(12) |
09:55-10:20 |
既存点までの距離誤差を最小にする点位置発見アルゴリズム |
○中村茂幹・浅野哲夫(北陸先端大)・Siu-Wing Cheng(HKUST) |
(13) |
10:20-10:40 |
直線のアレンジメントの走査に対する作業領域調節可能アルゴリズム |
○清井孝裕・浅野哲夫(北陸先端大) |
|
10:40-11:00 |
休憩 ( 20分 ) |
(14) |
11:00-11:25 |
劣線形時間ケーキ分割アルゴリズム |
○上田孝弘(京大)・伊藤大雄(電通大) |
(15) |
11:25-11:50 |
Efficient Algorithms for Sorting $k$-Sets in Bins |
Kazuhisa Seto(Seikei Univ.)・○Junichi Teruyama(NII)・Atsuki Nagao(Kyoto Univ.) |
|
11:50-13:20 |
休憩 ( 90分 ) |
12月21日(土) 午後 13:20 - 16:55 |
(16) |
13:20-13:45 |
k-Edge-Rigid Body-Hinge Graphs |
Yuya Higashikawa・Naoki Katoh・○Yuki Kobayashi(Kyoto Univ.)・Adnan Sljoka(York Univ.) |
(17) |
13:45-14:10 |
k-Sink Location Problem in Dynamic Path Networks |
○Yuya Higashikawa(Kyoto Univ.)・Mordecai J. Golin(HKUST)・Naoki Katoh(Kyoto Univ.) |
|
14:10-14:30 |
休憩 ( 20分 ) |
(18) |
14:30-14:55 |
A New Automaton Construction using Prefixes and Suffixes of Regular Expressions |
○Hiroaki Yamamoto(Shinshu Univ.) |
(19) |
14:55-15:20 |
On alternation-bounded alternating context-free grammars and languages |
○Etsuro Moriya(Waseda Univ.) |
(20) |
15:20-15:45 |
接頭辞集合に対する決定性有限オートマトンの最小無矛盾問題について |
○上埜かおり(東北大)・下薗真一(九工大)・成澤和志・篠原 歩(東北大) |
|
15:45-16:05 |
休憩 ( 20分 ) |
(21) |
16:05-16:30 |
次数制約のあるグラフ有向化問題の近似について |
○朝廣雄一(九州産大)・ジェスパー ジャンソン(京大)・宮野英次(九工大)・小野廣隆(九大) |
(22) |
16:30-16:55 |
回転する地図上の正方形ラベルに対するラベルサイズ最大化 |
○横須賀佑介・今井桂子(中大) |