Decomposition of submodular functions |
| |
Authors: | William H. Cunningham |
| |
Affiliation: | (1) Department of Mathematics and Statistics, Carleton University, Ottawa, Canada |
| |
Abstract: | A decomposition theory for submodular functions is described. Any such function is shown to have a unique decomposition consisting of indecomposable functions and certain highly decomposable functions, and the latter are completely characterized. Applications include decompositions of hypergraphs based on edge and vertex connectivity, the decomposition of matroids based on three-connectivity, the Gomory—Hu decomposition of flow networks, and Fujishige’s decomposition of symmetric submodular functions. Efficient decomposition algorithms are also discussed. |
| |
Keywords: | 05 C 99 05 B 35, 68 E 99 |
本文献已被 SpringerLink 等数据库收录! |
|