On the monotonicity of games generated by symmetric submodular functions

Fedor V. Fomin; Dimitrios M. Thilikos

doi:10.1016/S0166-218X(02)00459-6

On the monotonicity of games generated by symmetric submodular functions

Fedor V. Fomin, Dimitrios M. Thilikos

Computer Science

Research output: Contribution to journal › Conference article › peer-review

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)
Pages (from-to)	323-335
Number of pages	13
Journal	Discrete Applied Mathematics
Volume	131
Issue number	2
DOIs	https://doi.org/10.1016/S0166-218X(02)00459-6
State	Published - Sep 12 2003
Event	Submodularity - Atlanta, GA, United States Duration: Aug 1 2000 → Aug 1 2000

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/S0166-218X(02)00459-6

Cite this

@article{185e9342d5cf4131a58083efc08d94ca,

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

year = "2003",

month = sep,

day = "12",

doi = "10.1016/S0166-218X(02)00459-6",

language = "English (US)",

volume = "131",

pages = "323--335",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "2",

note = "Submodularity ; Conference date: 01-08-2000 Through 01-08-2000",

}

TY - JOUR

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

AU - Fomin, Fedor V.

AU - Thilikos, Dimitrios M.

PY - 2003/9/12

Y1 - 2003/9/12

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=0041828775&partnerID=8YFLogxK

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

U2 - 10.1016/S0166-218X(02)00459-6

DO - 10.1016/S0166-218X(02)00459-6

M3 - Conference article

AN - SCOPUS:0041828775

SN - 0166-218X

VL - 131

SP - 323

EP - 335

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 2

T2 - Submodularity

Y2 - 1 August 2000 through 1 August 2000

ER -

On the monotonicity of games generated by symmetric submodular functions

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this