A Fast Parametric Submodular Intersection Algorithm for Strong Map Sequences
A Fast Parametric Submodular Intersection Algorithm for Strong Map Sequences
复制标题
强地图序列的快速参数子模交集算法
DOI：
10.1287/moor.22.4.803
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
Maiko Shigeno
中科院分区：
文献类型：
--
作者：
S. Iwata;K. Murota;Maiko Shigeno
本文给出了一个求解子模系统的非减非增强映射序列对的交问题的快速算法。最坏情况下的时间界限是相同的推/重新标记算法的一个单一的交叉问题。这扩展了Gallo-Grigoriadis-Tarjan GGT方法的参数最大流问题，并揭示了算法的意义的概念，强映射的次模系统。
This paper presents a fast algorithm to solve the intersection problem for a pair of nondecreasing and nonincreasing strong map sequences of submodular systems. The worst-case time bound is the same as that of the push/relabel algorithm for a single intersection problem. This extends the Gallo-Grigoriadis-Tarjan GGT method for parametric maximum flow problems and reveals an algorithmic significance of the concept of strong maps for submodular systems.