| Presentation | 2017-12-21 Space Efficient Algorithms for Maximum (Weight) Independent Set on Circular Arcs Shohei Urakawa, Tom C. van der Zanden, Toshiki Saitoh, Ryuhei Uehara, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Recently，due to increase of the capacity of storages，we require space efficient algorithms with a limited workspace for treating with huge amount of data． In this paper，we deal with the problems of finding the maximum weighted and unweighted independent set for a set of arcs on a circle，called circular arc representation． In this paper, we propose space efficient algorithms for maximum independent set problem on circular arc． The algorithm for the unweighted problem works in $ O (frac{n}{s} (n (frac{n}{s} + log s) + s^2)$ time，and the algorithm for the weighted problem works in $ O (n ^ {log {n / s} +1} (s log s + n log ^ * s + (n log n) / (log s)))$ time where the input size is $ n $, and the workspace is $ O (s) $ words ($ s |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | circular arc / interval / maximum independent set / space efficient algorithm |
| Paper # | ISEC2017-74,COMP2017-28 |
| 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) | Space Efficient Algorithms for Maximum (Weight) Independent Set on Circular Arcs |
| Sub Title (in English) | |
| Keyword(1) | circular arc |
| Keyword(2) | interval |
| Keyword(3) | maximum independent set |
| Keyword(4) | space efficient algorithm |
| 1st Author's Name | Shohei Urakawa |
| 1st Author's Affiliation | Kobe University(Kobe Univ.) |
| 2nd Author's Name | Tom C. van der Zanden |
| 2nd Author's Affiliation | Utrecht University(Utrecht Univ.) |
| 3rd Author's Name | Toshiki Saitoh |
| 3rd Author's Affiliation | Kyushu Institute of Technology(Kyutech) |
| 4th Author's Name | Ryuhei Uehara |
| 4th Author's Affiliation | Japan Advanced Institute of Science and Technology(JAIST) |
| Date | 2017-12-21 |
| Paper # | ISEC2017-74,COMP2017-28 |
| Volume (vol) | vol.117 |
| Number (no) | ISEC-369,COMP-370 |
| Page | pp.pp.11-18(ISEC), pp.11-18(COMP), |
| #Pages | 8 |
| Date of Issue | 2017-12-14 (ISEC, COMP) |