ALCOMFT-TR-01-166

Fedor V. Fomin and Dimitrios M. Thilikos
On the Monotonicity of Games Generated by Symmetric Submodular Functions
Barcelona. Work packages 2 and 4. June 2001.

Abstract: Submodular functions have appeared to be a key tool for proving the monotonicity of several graph searching games. In this paper we provide a general game theoretic framework able to unify old and new monotonicity results in a unique min-max theorem. Our theorem, provides a game theoretic analogue to a wide number of graph theoretic parameters such as linear-width and cutwidth.

Postscript file: ALCOMFT-TR-01-166.ps.gz (103 kb).