On the monotonicity of games generated by symmetric submodular functions

Consultar RECERCAT

Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/97642

Título:	On the monotonicity of games generated by symmetric submodular functions
Autor/a:	Fomin, Fedor V.; Thilikos Touloupas, Dimitrios
Otros autores:	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.
Materia(s):	-Àrees temàtiques de la UPC::Informàtica -Submodularity -Linear-width -Cutwidth -Search games
Derechos:
Tipo de documento:	Artículo - Versión publicada Informe
Compartir:

Fomin, Fedor V.; Thilikos Touloupas, Dimitrios

Fomin, Fedor V.; Thilikos Touloupas, Dimitrios

Demaine, Erik D.; Fomin, Fedor V.; Hajiaghayi, Mohammad Taghi; Thilikos Touloupas, Dimitrios

Thilikos Touloupas, Dimitrios; Fomin, Fedor V.

Fomin, Fedor V.; Thilikos Touloupas, Dimitrios

Coordinación

Patrocinio