Convolution and Dilworth truncation of submodular functions

H NARAYANAN

Abstract


In this paper we survey the many applications of the operations of convolution and Dilworth truncation of submodular functions. Among other things we discuss in detail the strong analogies that exist between structural results related to the two operation, in particular those that exist between the principal partition of submodular function with respect to a positive weight function and the principal lattice of partitions of submodular function.

Keywords


Submodular functions; polymalroids; malroids; convolution; Dilworth truncation.

Full Text:

PDF

Refbacks

  • There are currently no refbacks.