optimization - 所有对最大不相交路径算法

Question

假设在一个无向图中有多个源目的地对。我想为多对生成不相交的路径。这样的问题的复杂性是什么？是否有任何多项式启发式方法可以找到这些对的边缘不相交路径？ (即 s1 和 d1 之间的路径不应与 s2 和 d2 之间的路径有任何共同边)

Answer 1

这看起来像是多商品流问题的变体:http://en.wikipedia.org/wiki/Multi-commodity_flow_problem

将每个源/汇对视为一种新商品，并赋予边缘单位权重以强制执行不相交的路径。现在在文献中搜索具有单位容量的此类 MCFP 的近似值。