.png){kind=icon}
返回
On the K best integer network flows
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2012.08.014.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
We address the problem of finding the K best integer solutions of a linear integer network flow problem. We design an O(f(n,m,L,U)+KmS(n,m,L)) time and O(K+m) memory space algorithm to determine the K best integer solutions, in a directed network with n nodes, m arcs, maximum absolute value cost L, and an upper bound U on arc capacities and node supplies. f(n,m,L,U) is the best time needed to solve the minimum cost flow problem in a directed network and S(n,m,L) is the best time to solve the single-source shortest path problem in a network with non-negative lengths. The introduced algorithm efficiently determines a proper minimal cycle by taking advantage of the relationship between the best solutions. This way, we improve the theoretical as well as practical memory space bounds of the well-known method due to Hamacher. Our computational experiments confirm this result. (C) 2012 Elsevier Ltd. All rights reserved.
Keyword:
Combinatorial optimization
K best integer network flow problem
Minimum cost flow problem
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
C
IF:
4.3
论文数:
6.5K
被引数:
1.8W
机构
暂无机构信息
引用论文
.png){kind=icon}
查看更多内容