Bounds on the Geometric Mean of Arc Lengths for Bounded-Degree Planar Graphs
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Hasan, Mohammad Khairul | - |
| dc.contributor.author | Yoon, Sung-Eui | - |
| dc.contributor.author | Chwa, Kyung-Yong | - |
| dc.date.accessioned | 2011-06-29T02:07:44Z | - |
| dc.date.available | 2011-06-29T02:07:44Z | - |
| dc.date.issued | 2011-06-29 | - |
| dc.identifier.uri | http://hdl.handle.net/10203/24265 | - |
| dc.description.abstract | Data access time becomes the main bottleneck in applications dealing with large-scale graphs. Cache-oblivious layouts, constructed to minimize the geometric mean of arc lengths of graphs, have been adapted to reduce data access time during random walks on graphs. In this paper, we present a constant factor approximation algorithm for the Minimum Geometric Mean Layout (MGML) problem for bounded-degree planar graphs. We also derive an upper bound for any layout of the MGML problem. To the best of our knowledge, these are the first results for the MGML problem with bounded-degree planar graphs. | en |
| dc.description.sponsorship | We would like to thank Peter Lindstrom, who first identified that the geometric means of space-filling curves of grids converge to a constant, as the grid size increases. This observation strongly supported that there is possibility that we can have a constant-factor approximation algorithm in terms of minimizing the geometric means. We also thank Samuel Brice and group members of the KAIST Theory of Computation for their English review and helpful feedbacks. This project was supported in part by KAIST, MKE/MCST/IITA [2008-F- 033-02], MKE/IITA u-Learning, MKE digital mask control, MCST/KOCCACTR& DP-2009, KRF-2008-313-D00922, MSRA E-heritage, and DAPA&ADD contract(UD080042AD). | en |
| dc.language.iso | en_US | en |
| dc.title | Bounds on the Geometric Mean of Arc Lengths for Bounded-Degree Planar Graphs | en |
| dc.type | Article | en |
- Appears in Collection
- CS-Journal Papers(저널논문)
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.