On the monotonicity of games generated by symmetric submodular functions

Fedor V. Fomin; Dimitrios M. Thilikos

doi:10.1007/3-540-45477-2_17

On the monotonicity of games generated by symmetric submodular functions

Fedor V. Fomin, Dimitrios M. Thilikos

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English (US)
Title of host publication	Graph-Theoretic Concepts in Computer Science - 27th International Workshop, WG 2001, Proceedings
Editors	Andreas Brandstadt, Van Bang Le
Publisher	Springer Verlag
Pages	177-188
Number of pages	12
ISBN (Print)	3540427074, 9783540427070
DOIs	https://doi.org/10.1007/3-540-45477-2_17
State	Published - 2001
Event	27th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2001 - Boltenhagen, Germany Duration: Jun 14 2001 → Jun 16 2001

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2204
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	27th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2001
Country/Territory	Germany
City	Boltenhagen
Period	6/14/01 → 6/16/01

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-45477-2_17

Cite this

Fomin, F. V., & Thilikos, D. M. (2001). On the monotonicity of games generated by symmetric submodular functions. In A. Brandstadt, & V. B. Le (Eds.), Graph-Theoretic Concepts in Computer Science - 27th International Workshop, WG 2001, Proceedings (pp. 177-188). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2204). Springer Verlag. https://doi.org/10.1007/3-540-45477-2_17

On the monotonicity of games generated by symmetric submodular functions. / Fomin, Fedor V.; Thilikos, Dimitrios M.
Graph-Theoretic Concepts in Computer Science - 27th International Workshop, WG 2001, Proceedings. ed. / Andreas Brandstadt; Van Bang Le. Springer Verlag, 2001. p. 177-188 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2204).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Fomin, FV & Thilikos, DM 2001, On the monotonicity of games generated by symmetric submodular functions. in A Brandstadt & VB Le (eds), Graph-Theoretic Concepts in Computer Science - 27th International Workshop, WG 2001, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2204, Springer Verlag, pp. 177-188, 27th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2001, Boltenhagen, Germany, 6/14/01. https://doi.org/10.1007/3-540-45477-2_17

Fomin FV, Thilikos DM. On the monotonicity of games generated by symmetric submodular functions. In Brandstadt A, Le VB, editors, Graph-Theoretic Concepts in Computer Science - 27th International Workshop, WG 2001, Proceedings. Springer Verlag. 2001. p. 177-188. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-45477-2_17

Fomin, Fedor V. ; Thilikos, Dimitrios M. / On the monotonicity of games generated by symmetric submodular functions. Graph-Theoretic Concepts in Computer Science - 27th International Workshop, WG 2001, Proceedings. editor / Andreas Brandstadt ; Van Bang Le. Springer Verlag, 2001. pp. 177-188 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{690455f67e9b40a9993559e7b93f2329,

title = "On the monotonicity of games generated by symmetric submodular functions",

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.",

author = "Fomin, {Fedor V.} and Thilikos, {Dimitrios M.}",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2001.; 27th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2001 ; Conference date: 14-06-2001 Through 16-06-2001",

year = "2001",

doi = "10.1007/3-540-45477-2_17",

language = "English (US)",

isbn = "3540427074",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "177--188",

editor = "Andreas Brandstadt and Le, {Van Bang}",

booktitle = "Graph-Theoretic Concepts in Computer Science - 27th International Workshop, WG 2001, Proceedings",

}

TY - GEN

T1 - On the monotonicity of games generated by symmetric submodular functions

AU - Fomin, Fedor V.

AU - Thilikos, Dimitrios M.

N1 - Publisher Copyright: © Springer-Verlag Berlin Heidelberg 2001.

PY - 2001

Y1 - 2001

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84945268059&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84945268059&partnerID=8YFLogxK

U2 - 10.1007/3-540-45477-2_17

DO - 10.1007/3-540-45477-2_17

M3 - Conference contribution

AN - SCOPUS:84945268059

SN - 3540427074

SN - 9783540427070

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 177

EP - 188

BT - Graph-Theoretic Concepts in Computer Science - 27th International Workshop, WG 2001, Proceedings

A2 - Brandstadt, Andreas

A2 - Le, Van Bang

PB - Springer Verlag

T2 - 27th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2001

Y2 - 14 June 2001 through 16 June 2001

ER -

On the monotonicity of games generated by symmetric submodular functions

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this