.png){kind=icon}
返回
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
摘要
En 中文
We introduce a new approach to the maximum flow problem. This approach is based on assigning arc lengths based on the residual flow value and the residual arc capacities. Our approach leads to an
O
(min(
n
2/3
,
m
1/2
)
m
log(
n
2
/
m
) log
U
) time bound for a network with
n
vertices,
m
arcs, and integral arc capacities in the range [1, …,
U
]. This is a fundamental improvement over the previous time bounds. We also improve bounds for the Gomory-Hu tree problem, the parametric flow problem, and the approximate
s-t
cut problem.
期刊
暂无期刊信息
机构
暂无机构信息
引用论文
暂无论文信息