Submodular flows and applications
Lists
Only you see this
Abstract
Several recent combinatorial studies involving submodularity fit into the following pattern. Take a classical graph-theoretical result (e.g. the Marriage Theorem, the Max-flow-min-cut Theorem etc.), and replace certain linear functions occurring in the problem (either in the objective function or in the constraints) by submodular functions. Often the generalizations of the original theorems obtained this way remain valid; sometimes even the proofs carry over. What is important here to realize is that these generalizations are by no means l'art pour l'art. In fact, the range of applicability of certain methods can be extended tremendously by this trick.
BibTeX
@inproceedings{lau2011submodular,
author = {Lap Chi Lau and R. Ravi and Mohit Singh},
title = {{Submodular flows and applications}},
booktitle = {Cambridge},
year = {2011},
doi = {10.1017/cbo9780511977152.008},
}Loading related content...