solidot新版网站常见问题,请点击这里查看。
消息
本文已被查看13492次
Flow-Cut Gaps and Face Covers in Planar Graphs. (arXiv:1811.02685v1 [cs.DS])
来源于:arXiv
The relationship between the sparsest cut and the maximum concurrent
multi-flow in graphs has been studied extensively. For general graphs with $k$
terminal pairs, the flow-cut gap is $O(\log k)$, and this is tight. But when
topological restrictions are placed on the flow network, the situation is far
less clear. In particular, it has been conjectured that the flow-cut gap in
planar networks is $O(1)$, while the known bounds place the gap somewhere
between $2$ (Lee and Raghavendra, 2003) and $O(\sqrt{\log k})$ (Rao, 1999).
A seminal result of Okamura and Seymour (1981) shows that when all the
terminals of a planar network lie on a single face, the flow-cut gap is exactly
$1$. This setting can be generalized by considering planar networks where the
terminals lie on $\gamma>1$ faces in some fixed planar drawing. Lee and
Sidiropoulos (2009) proved that the flow-cut gap is bounded by a function of
$\gamma$, and Chekuri, Shepherd, and Weibel (2013) showed that the gap is at
most $3\gamma 查看全文>>