首页> 外文会议>Frontiers in algorithmics >Bounds on the Geometric Mean of Arc Lengths for Bounded-Degree Planar Graphs
【24h】

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

机译:有界平面图的弧长几何平均值的界

获取原文
获取原文并翻译 | 示例

摘要

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.
机译:数据访问时间成为处理大型图形的应用程序中的主要瓶颈。构造为使图形的圆弧长度的几何均值最小化的不考虑缓存的布局已被调整为减少图形随机游走期间的数据访问时间。在本文中,我们为有界平面图的最小几何均值布局(MGML)问题提出了一种恒定因子近似算法。我们还得出了MGML问题的任何布局的上限。据我们所知,这是带界平面图的MGML问题的第一个结果。

著录项

  • 来源
    《Frontiers in algorithmics》|2009年|153-162|共10页
  • 会议地点 Hefei(CN);Hefei(CN)
  • 作者单位

    Division of Computer Science Korea Advanced Institute of Science and Technology (KAIST), Republic of Korea;

    Division of Computer Science Korea Advanced Institute of Science and Technology (KAIST), Republic of Korea;

    Division of Computer Science Korea Advanced Institute of Science and Technology (KAIST), Republic of Korea;

  • 会议组织
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 计算技术、计算机技术;
  • 关键词

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号