| Presentation | 2010-03-12 Online graph exploration algorithms for cycles and trees by multiple number of searchers Yuya HIGASHIKAWA, Naoki KATOH, Shin-ichi TANIGAWA, Stefan LANGERMAN, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | This paper deals with online graph exploration problems by muitiple searchers. The purpose of search is to visit all vertices by at least one searcher. It is assumed that searchers stay at the origin at the beginning and start to explore a graph with the same speed, and that they can communicate with each other to share the whole information gathered by at least one searcher. We consider two cases of graphs, cycles and trees. For cycles, we establish an optimal algorithm of 3/2-competitive ratio with two searchers. For trees, we establish an optimal algorithm with P searchers of (p/(log p))+o(1)-competitive ratio. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | online algorithm / competitive analysis / vertex search problem |
| Paper # | COMP2009-57 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2010/3/5(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Online graph exploration algorithms for cycles and trees by multiple number of searchers |
| Sub Title (in English) | |
| Keyword(1) | online algorithm |
| Keyword(2) | competitive analysis |
| Keyword(3) | vertex search problem |
| 1st Author's Name | Yuya HIGASHIKAWA |
| 1st Author's Affiliation | Department of Architecture and Architectural Engineering, Kyoto University() |
| 2nd Author's Name | Naoki KATOH |
| 2nd Author's Affiliation | Department of Architecture and Architectural Engineering, Kyoto University |
| 3rd Author's Name | Shin-ichi TANIGAWA |
| 3rd Author's Affiliation | Department of Architecture and Architectural Engineering, Kyoto University |
| 4th Author's Name | Stefan LANGERMAN |
| 4th Author's Affiliation | Maitre de Recherches F.R.S.-FNRS, Departement d'Informatique, Univesite Libre de Bruxells |
| Date | 2010-03-12 |
| Paper # | COMP2009-57 |
| Volume (vol) | vol.109 |
| Number (no) | 465 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |