Fri, Dec 20 Day 1 09:25 - |
Fri, Dec 20 AM 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 |
Break ( 15 min. ) |
(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 |
Break ( 90 min. ) |
Fri, Dec 20 PM 13:20 - 16:50 |
(6) |
13:20-13:45 |
On the Extension of the Serial Dictatorship with Project Closures |
Naoyuki Kamiyama (Kyushu Univ.) |
(7) |
13:45-14:10 |
A Power Allocation Management System Using an Algorithm for the Knapsack Problem |
Naoyuki Morimoto, Yuu Fujita, Masaaki Yoshida, Hiroyuki Yoshimizu, Masafumi Takiyamada, Terukazu Akehi, Masami Tanaka (Enegate) |
|
14:10-14:25 |
Break ( 15 min. ) |
(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 |
Break ( 15 min. ) |
(10) |
15:30-16:50 |
[Tutorial Lecture]
Introduction to Computational Complexity Theory (5): Approaches to P vs. NP via Circuits |
Kazuhisa Seto (Seikei Univ.) |
Sat, Dec 21 Day 2 09:25 - 16:50 |
Sat, Dec 21 AM 09:30 - 11:50 |
(11) |
09:30-09:55 |
An Adjustable Work Space Algorithm for Finding a Shortest Path in a Simple Polygon |
Matsuo Konagaya, Tetsuo Asano (JAIST), Otfried Cheong (KAIST), Sang Won Bae (Kyonggi Univ.) |
(12) |
09:55-10:20 |
An Algorithm for Finding the Point Minimizing the Distance Error to Given Points |
Shigeki Nakamura, Tetsuo Asano (JAIST), Siu-Wing Cheng (HKUST) |
(13) |
10:20-10:40 |
Adjustable Work Space Algorithm of Arrangement of Lines |
Takahiro Seii, Tetsuo Asano (JAIST) |
|
10:40-11:00 |
Break ( 20 min. ) |
(14) |
11:00-11:25 |
Sublinear-time cake-cutting algorithms |
Takahiro Ueda (Kyoto Univ.), Hiro Ito (Univ. of Electro-Comm.) |
(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 |
Break ( 90 min. ) |
Sat, Dec 21 PM 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 |
Break ( 20 min. ) |
(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 |
On the minimum consistent DFA problem for prefix samples |
Kaori Ueno (Tohokui Univ.), Shinichi Shimozono (Kyushu Inst. of Tech.), Kazuyuki Narisawa, Ayumi Shinohara (Tohokui Univ.) |
|
15:45-16:05 |
Break ( 20 min. ) |
(21) |
16:05-16:30 |
Approximability of graph orientation problems with degree constraints |
Yuichi Asahiro (Kyushu Sangyo Univ.), Jesper Jansson (Kyoto Univ.), Eiji Miyano (Kyushu Institute of Technology), Hirotaka Ono (Kyushu Univ.) |
(22) |
16:30-16:55 |
Label Size Maximization for Square Labels on Rotating Maps |
Yusuke Yokosuka, Keiko Imai (Chuo Univ.) |