...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >Two-segmented channel routing is strong NP-complete
【24h】

Two-segmented channel routing is strong NP-complete

机译：两段式通道路由功能强大，NP完整

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Two-segmented channel routing is a special case of segmented channel routing where each net connection is restricted to occupying two track segments at most. In order to achieve various performance measures in a design, such a restriction is sometimes necessary. Segmented channel routing problems come from the wiring of field programmable gate arrays (FPGAs) and are known to be NP-complete in the strong sense. However, whether the special case 2-segmented channel routing remains NP-complete in the strong sense or not has not been proved. In this paper, we show that the 2-segmented channel routing problem remains strongly NP-complete, and thus an efficient optimal algorithm for this special case of the segmented channel routing problem is unfortunately unlikely to exist. Our technique holds also for the case where connection lengths are bounded and settles an open question raised in Gamal et al. (1991), Li (1995), and Roychowdhury (1993).
机译：两段通道路由是段通道路由的一种特殊情况，其中每个网络连接被限制为最多占用两个磁道段。为了在设计中实现各种性能指标，有时需要这种限制。分段通道路由问题来自现场可编程门阵列（FPGA）的布线，从严格意义上讲，它是NP完整的。但是，还没有证明特殊情况下2段通道路由是否在强意义上仍保持NP完整。在本文中，我们表明2段通道路由问题仍然具有很强的NP完全性，因此不幸的是，对于这种特殊情况的段通道路由问题，几乎不可能存在有效的最优算法。我们的技术还适用于连接长度有界的情况，并解决了Gamal等人提出的一个开放性问题。 （1991），李（1995）和罗伊休杜里（1993）。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号