On the monotonicity of games generated by symmetric submodular functions.
type: Item
instance of: scholarly article
title: On the monotonicity of games generated by symmetric submodular functions.
zbMATH Open document ID: 1069.91019
DOI: 10.1016/S0166-218X(02)00459-6
author: Dimitrios M. Thilikos
author: Fedor V. Fomin
published in: Discrete Applied Mathematics
publication date: 2003-10-14T00:00:00Z
review text: A graph searching game has as objective to capture an omniscient fugitive residing on the vertices or/and edges of a graph by systematically moving a specific number of searchers on it. In the majority of the cases, the minimum number of searchers required to capture the fugitive is equivalent to some known graph theoretical parameter. In this paper it is shown how a graph parameter can be generated by a connectivity function and a general minimax theorem that characterizes it is provided.
Mathematics Subject Classification ID: 91A43
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 1992933
zbMATH Keywords: graph
zbMATH Keywords: connectivity function
zbMATH Keywords: searching game
Wikidata QID: Q60488779
reviewed by: Anton Ştefănescu
MaRDI profile type: Publication
cites work: The congestion of \(n\)-cube layout on a rectangular grid
cites work: Q4035355
cites work: Quickly excluding a forest
cites work: Monotonicity in graph searching
cites work: Q3852212
cites work: The bandwidth problem for graphs and matrices—a survey
cites work: Fugitive-search games on graphs and related parameters
cites work: The vertex separation and search number of a graph
cites work: Graph searching and interval completion
cites work: A Sufficient Condition for Backtrack-Free Search
cites work: The vertex separation number of a graph equals its path-width
cites work: Interval graphs and searching
cites work: Searching and pebbling
cites work: The Linkage of a Graph
cites work: Recontamination does not help to search a graph
cites work: On minimizing width in linear layouts
cites work: The complexity of searching a graph
cites work: Q3477966
cites work: Graph minors. X: Obstructions to tree-decomposition
cites work: Graph searching and a min-max theorem for tree-width
cites work: Call routing and the ratcatcher
cites work: Mixed searching and proper-path-width
cites work: Algorithms and obstructions for linear-width and related search parameters
full work available at URL: s0166-218x(02)00459-6
OpenAlex ID: W2089401485
description: scientific article; zbMATH DE number 1992933