On the monotonicity of games generated by symmetric submodular functions

All of RECERCAT

To access the full text documents, please follow this link: http://hdl.handle.net/2117/97642

Title:	On the monotonicity of games generated by symmetric submodular functions
Author:	Fomin, Fedor V.; Thilikos Touloupas, Dimitrios
Other authors:	Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
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.
Subject(s):	-Àrees temàtiques de la UPC::Informàtica -Submodularity -Linear-width -Cutwidth -Search games
Rights:
Document type:	Article - Published version Report
Share: