| Presentation | 2017-12-21 O(n^{1/3})-space algorithm for the grid graph reachability problem Ryo Ashida, Kotaro Nakagawa, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The directed graph reachability problem is a canonical complete problem for class NL. The best known polynomial time algorithm for this problem by Barns et al. uses $O(n/2^{sqrt{log{n}}})$ space. Whether we can make $O(n^eps)$-space and polynomial time algorithm for some $eps < 1$ is a famous open problem. For some restricted graph classes of directed graphs, better results are known. Asano et al. gave an $widetilde{O}(sqrt{n})$ space and polynomial time algorithm for the reachability problem restricted to directed grid and planar graphs. We propose an $widetilde{O}(n^{1/3})$ space and polynomial time algorithm for the reachability problem restricted to directed grid graphs. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | graph algorithm / graph reachability / grid graph / sub-linear space algorithm |
| Paper # | ISEC2017-75,COMP2017-29 |
| Date of Issue | 2017-12-14 (ISEC, COMP) |
| Conference Information | |
| Committee | ISEC / COMP |
|---|---|
| Conference Date | 2017/12/21(2days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Eikokuji Campus, Kochi University of Technology |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Kazuto Ogawa(NHK) / Hiro Ito(Univ. of Electro-Comm.) |
| Vice Chair | Atsushi Fujioka(Kanagawa Univ.) / Shiho Moriai(NICT) / Yushi Uno(Osaka Pref. Univ.) |
| Secretary | Atsushi Fujioka(Tohoku Univ.) / Shiho Moriai(Tokai Univ.) / Yushi Uno(Seikei Univ.) |
| Assistant | Keita Emura(NICT) / Yuichi Komano(TOSHIBA) / Yuuji Suga(IIJ) |
| Paper Information | |
| Registration To | Technical Committee on Information Security / Technical Committee on Theoretical Foundations of Computing |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | O(n^{1/3})-space algorithm for the grid graph reachability problem |
| Sub Title (in English) | |
| Keyword(1) | graph algorithm |
| Keyword(2) | graph reachability |
| Keyword(3) | grid graph |
| Keyword(4) | sub-linear space algorithm |
| 1st Author's Name | Ryo Ashida |
| 1st Author's Affiliation | Tokyo Institute of Technology(Tokyo Tech) |
| 2nd Author's Name | Kotaro Nakagawa |
| 2nd Author's Affiliation | Tokyo Institute of Technology(Tokyo Tech) |
| Date | 2017-12-21 |
| Paper # | ISEC2017-75,COMP2017-29 |
| Volume (vol) | vol.117 |
| Number (no) | ISEC-369,COMP-370 |
| Page | pp.pp.19-24(ISEC), pp.19-24(COMP), |
| #Pages | 6 |
| Date of Issue | 2017-12-14 (ISEC, COMP) |