Polynomial-time algorithms for special cases of the maximum confluent flow problem

详细信息    查看全文

• 作者：Daniel Dressler ; Martin Strehler
• 关键词：Confluent flow ; Outerplanar graph ; Polynomial-time algorithm ; Treewidth ; FPTAS
• 刊名：Discrete Applied Mathematics
• 出版年：30 January, 2014
• 年：2014
• 卷：163
• 期：part_P2
• 页码：142-154
• 全文大小：482 K

文摘

A flow on a directed network is said to be confluent if the flow uses at most one outgoing arc at each node. Confluent flows arise naturally in destination-based routing. We study the maximum confluent flow problem (MaxConf) with a single commodity but multiple sources and sinks and heterogeneous arc capacities. It was recently shown that MaxConf 聽is -hard even on trees. We improve the classification of easy and hard confluent flow problems by providing polynomial-time algorithms for outerplanar graphs with a single sink, as well as trees with a constant number of either sources or sinks. Furthermore, we present an FPTAS for graphs with bounded treewidth.