We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
A FAST PARAMETRIC SUBMODULAR INTERSECTION ALGORITHM FOR STRONG MAP SEQUENCES.
- Authors
Iwata, Satoru; Murota, Kazuo; Shigeno, Maiko
- Abstract
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.
- Subjects
ALGORITHMS; SUBMODULAR functions; MATHEMATICAL models; MATROIDS; PARAMETRIC vibration; ALGEBRA; FOUNDATIONS of arithmetic
- Publication
Mathematics of Operations Research, 1997, Vol 22, Issue 4, p803
- ISSN
0364-765X
- Publication type
Article
- DOI
10.1287/moor.22.4.803