A Fast Parametric Submodular Intersection Algorithm for Strong Map Sequences
Satoru Iwata, Kazuo Murota, Maiko Shigeno · Mathematics of Operations Research · 1997
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.