文件名称:Manhattan

  • 所属分类:
  • 数据结构常用算法
  • 资源属性:
  • [PDF]
  • 上传时间:
  • 2012-11-26
  • 文件大小:
  • 582kb
  • 下载次数:
  • 0次
  • 提 供 者:
  • 东**
  • 相关连接:
  • 下载说明:
  • 别用迅雷下载,失败请重下,重下不扣分!

介绍说明--下载内容均来自于网络,请自行研究使用

在 VLSI 设计中,多点互连是物理设计阶段的关键问题之一,而互连的点数等于 2 或大于 2 分别对应于

Manhattan 空间上有障碍时的最短路径问题和最小 Steiner 树问题,显然前者是后者的基础.连接图是研究最短路径

问题的有效工具,已有的典型连接图包括基于轨迹的GC 和GT 以及基于自由区的GF 和GG.工作包括3个方面:设计并分析了在各种连接图上实现动态的点对之间的最短路径查询算法 分析了在各个连接图上构造 3-Steiner 树的算

法,对于已有的 GC 上的 3-Steiner 算法,将其 Steiner 顶点的候选集合规模从 O((e+p)

2

)降低到了 O((t+p)

2

),其中 e,t,p

分别表示边数、障碍极边数和顶点数 设计了在GG上的3-Steiner树构造算法,其平均情况时间复杂度只有Θ(t). -Abstract:  Finding networks with minimal cost to connect points is a key problem in VLSI design, which can be

described as obstacle-avoiding shortest path and minimum Steiner tree problem according to whether the number of

points is greater than 2. Connection graphs, such as track based on graphs GC  and GT  and free area based graphs

GF and GG, are effective tools for the shortest path problem, which is the foundation of the Steiner tree problem.

The contribution of this paper includes three points: The dynamic algorithms for querying the shortest path between

two points on each connection graph are designed and analyzed for the first time  secondly, all algorithms for

Steiner problem on each connection graph are analyzed The number of candidate Steiner points is reduced from

O((e+p)

2

) to O((t+p)

2

) in the 3-Steiner algorithm on GC, where e, t, p presents the number of edges, extreme edges

of obstacles and terminals An average Θ(t) algorithm for
相关搜索: steiner

(系统自动生成,下载前可以参看下载内容)

下载文件列表

On Optimal Rectilinear Shortest Paths and 3-Steiner Tree Routing in Presence of Obstacles.PDF

相关说明

  • 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
  • 本站是交换下载平台,提供交流渠道,下载内容来自于网络,除下载问题外,其它问题请自行百度更多...
  • 请直接用浏览器下载本站内容,不要使用迅雷之类的下载软件,用WinRAR最新版进行解压.
  • 如果您发现内容无法下载,请稍后再次尝试;或者到消费记录里找到下载记录反馈给我们.
  • 下载后发现下载的内容跟说明不相乎,请到消费记录里找到下载记录反馈给我们,经确认后退回积分.
  • 如下载前有疑问,可以通过点击"提供者"的名字,查看对方的联系方式,联系对方咨询.

相关评论

暂无评论内容.

发表评论

*主  题:
*内  容:
*验 证 码:

源码中国 www.ymcn.org