...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >An efficient algorithm for the evacuation problem in a certain class ofnetworks with uniform path-lengths
【24h】

An efficient algorithm for the evacuation problem in a certain class ofnetworks with uniform path-lengths

机译：路径长度均匀的一类网络中疏散问题的有效算法

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

摘要

In this paper, we consider the evacuation problem in a network which consists of a directedgraph with capacities and transit times on its arcs. This problem can be solved by thealgorithm of Hoppe and Tardos [B. Hoppe, E. Tardos, The quickest transshipment problem,Math. Oper. Res. 25(1) (2000) 36-62] in polynomial time. However their running time ishigh-order polynomial, and hence is not practical in general. Thus, it is necessary to devisea faster algorithm for a tractable and practically useful subclass of this problem. In thispaper, we consider a network with a sink s such that (i) for each vertex v s the sumof the transit times of arcs on any path from v to s takes the same value, and (ii) for each vertex v s the minimum v-s cut is determined by the arcs incident to s whose tails arereachable from v. This class of networks is a generalization of grid networks studied in thepaper [N. Kamiyama, N. Katoh, A. Takizawa, An efficient algorithm for evacuation problemin dynamic network flows with uniform arc capacity, IEICE Trans. Infrom. Syst. E89-D (8)(2006) 2372-2379]. We propose an efficient algorithm for this network problem.
机译：在本文中，我们考虑了一个网络中的疏散问题，该网络由一个在其弧上具有通行能力和穿越时间的有向图组成。这个问题可以通过Hoppe和Tardos的算法解决。 Hoppe，E。Tardos，最快的转运问题，数学。歌剧Res。 25（1）（2000）36-62]。但是，它们的运行时间是高阶多项式，因此通常不实用。因此，有必要设计一种更快的算法来解决该问题的易处理且实际有用的子类。在本文中，我们考虑一个具有汇点s的网络，使得（i）每个顶点与从v到s的任何路径上的弧的过渡时间之和取相同的值，并且（ii）每个顶点与最小值vs割线由入射到s的弧确定，该弧的尾部可从v到达。此类网络是本文研究的网格网络的概括。 Kamiyama，N. Katoh，A. Takizawa，一种有效的具有均匀电弧容量的动态网络流中疏散问题的算法，IEICE Trans。 Infrom。 Syst。 E89-D（8）（2006）2372-2379]。我们针对该网络问题提出了一种有效的算法。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号