New algorithms for the intersection problem of submodular systems
New algorithms for the intersection problem of submodular systems
复制标题
子模系统相交问题的新算法
DOI：
--
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
Xiaodong Zhang
中科院分区：
文献类型：
--
作者：
S. Fujishige;Xiaodong Zhang
本文研究了求两个子模系的最大公共子基的问题，|E| =n.首先，我们提出了一个新的算法，通过寻找最短的增广路径，它开始于一对给定的子模系统的子基，并方便采用Goldberg和Tarjan的预流推方法。其次，利用预流推方法的基本思想，设计了一个求交问题的快速算法，该算法在辅助图中每个顶点的弧表上采用最大标号实现，并按一定的顺序，总共需要O（n3）次推和O（n2）次重标号操作。
We consider the problem of finding a maximum common subbase of two submodular systems onE with |E|=n. First, we present a new algorithm by finding the shortest augmenting paths, which begins with a pair of subbases of the given submodular systems and is convenient for adopting the preflow-push approach of Goldberg and Tarjan. Secondly, by using the basic ideas of the preflow-push method, we devise a faster algorithm for the intersection problem, which requiresO(n3) push andO(n2) relabeling operations in total by the largest-label implementation with a specific order on the arc list of each vertex in the auxiliary graph.