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) |