| Presentation | 2014/11/13 Efficient Construction of Spanners and BFS Trees for Disk Transmission Graphs HAIM KAPLAN, WOLFGANG MULZER, LIAM RODITTY, PAUL SEIFERTH, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Let P ⊂ R^2 be a set of n points in the plane, each having an associated radius r_p > 0. This induces a directed graph T on P with an edge from p to q if and only if q lies in the disk with radius r_p around p. A t-spanner for T is sparse subgraph G of T that approximates each path: for any two vertices p, q connected in T by a path of length l, there path in G of length at most tl. For any constant t > 1, we show how to construct a t-spanner in time O(n(log n + log Φ)), where Φ is the spread of P (ratio of maximum to minimum pairwise distances in P) and where the constant hidden in the O-notation depends on t. Then, for any s ∈ P, we show how to use G to construct a BFS tree for T with root s within the same time bound. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | |
| Paper # | Vol.2014-AL-150 No.27 |
| Date of Issue |
| Conference Information | |
| Committee | MSS |
|---|---|
| Conference Date | 2014/11/13(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 | Mathematical Systems Science and its applications(MSS) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Efficient Construction of Spanners and BFS Trees for Disk Transmission Graphs |
| Sub Title (in English) | |
| Keyword(1) | |
| 1st Author's Name | HAIM KAPLAN |
| 1st Author's Affiliation | School of Computer Science, Tel Aviv University() |
| 2nd Author's Name | WOLFGANG MULZER |
| 2nd Author's Affiliation | Institut fur Informatik, Freie Universitat Berlin |
| 3rd Author's Name | LIAM RODITTY |
| 3rd Author's Affiliation | Department of Computer Science, Bar Ilan University |
| 4th Author's Name | PAUL SEIFERTH |
| 4th Author's Affiliation | Institut fur Informatik, Freie Universitat Berlin |
| Date | 2014/11/13 |
| Paper # | Vol.2014-AL-150 No.27 |
| Volume (vol) | vol.114 |
| Number (no) | 313 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |