首页 » 算法技术手册 » 算法技术手册全文在线阅读

《算法技术手册》分析

关灯直达底部

如果要能够高效地归约,那么必须高效地从原始问题映射到目标问题。二部图问题M=(S,T,P)可以在n+m+k步内转换成为一个图G=(V,E)。G有n+m+2个顶点以及n+m+k条边,因此图G的规模仅仅比原始二部图问题的规模大一个常数规模而已。这个重要特性决定了我们能够高效地求解二部图问题。一旦Ford-Fulkerson算法计算出最大流,那么网络中流为1的边对应着二部图中选择的匹配。要找到这些边只需要k步,所以需要O(k)的时间来将解映射成二部图问题的解。