.png){kind=icon}
返回
A polynomial time algorithm for the minimum flow problem in time-varying networks
.png){kind=icon}
PRE
AI
DOI：10.1007/s10479-017-2450-2.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
Flow variations over time generalize standard network flows by introducing an element of time. In contrast to the classical case of static flows, a flow over time in such a network specifies a flow rate entering an arc for each point in time. In this setting, the capacity of an arc limits the rate of flow into the arc at each point in time. Traditionally, flows over time are computed in time-expanded networks that contain one copy of the original network for each discrete time step. While this method makes available the whole algorithmic toolbox developed for static network flows, its drawback is the enormous size of the time-expanded network. In this paper, we extend the results about the minimum flow problem to network flows (with n nodes and m arcs) in which the time-varying lower bounds can involve both the source and the sink nodes (as in Fathabadi et al.) and also one additional node other than the source and the sink nodes. It is shown that this problem for the set {0,1,...,T} of time points can be solved by at most n minimum flow computations, by suitably extending the dynamic minimum flow algorithm and reoptimization techniques. The running time of the presented algorithm is O(n2m).
Keyword:
Network flows
Combinatorial optimization
(Dynamic) Minimum flow
(Dynamic) Preflow-pull algorithm
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
4.5
论文数:
8.1K
被引数:
2.1W
机构
引用论文
Novel 5′TOPmRNAs Regulated by Ribosomal S6 Kinase Are Important for Cardiomyocyte Development: S6 Kinase Suppression Limits Cardiac Differentiation and Promotes Pluripotent Cells Toward a Neural Lineage由核糖体S6激酶调控的新型5′TOPmRNAs对心肌细胞发育至关重要：S6激酶抑制限制了心脏分化并促进多能细胞向神经谱系分化
OAAI
OAAI分享收藏Parasympathetic baroreflexes and heart rate variability during acute stage of sport concussion recovery.png)
Brain Injury
Brain InjuryIF0
PREAI
分享收藏Frequency and risk factors for cognitive dysfunction in peritoneal dialysis patientsNephrology
NephrologyIF0
PREAI
分享收藏
查看更多内容