Carregant...
Carregant...

Vés al contingut (premeu Retorn)

On the monotonicity of games generated by symmetric submodular functions

Autor
Fomin, F.; Thilikos, D.
Tipus d'activitat
Document cientificotècnic
Data
2001-02
Codi
R01-5
Repositori
http://hdl.handle.net/2117/97642 Obrir en finestra nova
Resum
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.
Citació
Fomin, F., Thilikos, D. "On the monotonicity of games generated by symmetric submodular functions". 2001.
Paraules clau
Cutwidth, Linear-width, Search games, Submodularity
Grup de recerca
ALBCOM - Algorismia, Bioinformàtica, Complexitat i Mètodes Formals

Participants

  • Fomin, Fedor V.  (autor)
  • Thilikos Touloupas, Dimitrios  (autor)

Arxius