Bounds on the Geometric Mean of Arc Lengths for Bounded-Degree Planar Graphs

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 304
  • Download : 2
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.
Issue Date
2011-06-29
URI
http://hdl.handle.net/10203/24265
Appears in Collection
CS-Journal Papers(저널논문)

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0