On the monotonicity of games generated by symmetric submodular functions

Fedor V. Fomin, Dimitrios M. Thilikos

Research output: Contribution to journalConference articlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)323-335
Number of pages13
JournalDiscrete Applied Mathematics
Issue number2
StatePublished - Sep 12 2003
EventSubmodularity - Atlanta, GA, United States
Duration: Aug 1 2000Aug 1 2000

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'On the monotonicity of games generated by symmetric submodular functions'. Together they form a unique fingerprint.

Cite this