论文标题
平面图中的多商品流对面有需求
Multicommodity Flows in Planar Graphs with Demands on Faces
论文作者
论文摘要
我们考虑了平面图中多商品流的问题。西摩（Seymour）表明，如果供求图的结合是平面，那么切割条件就足以满足路线需求。 Okamura-Seymour表明，如果所有需求都出现在一个脸上，那么再次削减条件就足以满足路由需求。我们考虑了这些设置的共同概括，其中每个需求的终点位于平面图的同一面上。我们表明，如果图的每个面上的源接收器对，以致源和水槽在面部界定的周期上出现连续出现，那么流量切口间隙最多为3。我们提出了层次组合的脸部对层次组合的近似需求的概念，以证明这一结果。
We consider the problem of multicommodity flows in planar graphs. Seymour showed that if the union of supply and demand graphs is planar, then the cut condition is sufficient for routing demands. Okamura-Seymour showed that if all demands are incident on one face, then again cut condition is sufficient for routing demands. We consider a common generalization of these settings where the end points of each demand are on the same face of the planar graph. We show that if the source sink pairs on each face of the graph are such that sources and sinks appear contiguously on the cycle bounding the face, then the flow cut gap is at most 3. We come up with a notion of approximating demands on a face by convex combination of laminar demands to prove this result.
