On the monotonicity of games generated by symmetric submodular functions.

DOI10.1016/S0166-218X(02)00459-6zbMath1069.91019OpenAlexW2089401485WikidataQ60488779 ScholiaQ60488779MaRDI QIDQ1410686

Dimitrios M. Thilikos, Fedor V. Fomin

Publication date: 14 October 2003

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(02)00459-6

zbMATH Keywords

graphconnectivity functionsearching game

Mathematics Subject Classification ID

Games involving graphs (91A43) Graph theory (05C99) Connectivity (05C40)

Related Items (14)

Contraction obstructions for connected graph searching ⋮ A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth ⋮ Rank-width: algorithmic and structural results ⋮ Connected search for a lazy robber ⋮ The mixed search game against an agile and visible fugitive is monotone ⋮ Monotonicity of strong searching on digraphs ⋮ Digraph decompositions and monotonicity in digraph searching ⋮ Tangle and Maximal Ideal ⋮ An annotated bibliography on guaranteed graph searching ⋮ Monotonicity in digraph search problems ⋮ Connected graph searching ⋮ Directed path-width and monotonicity in digraph searching ⋮ Searching by heterogeneous agents ⋮ Submodular partition functions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Mixed searching and proper-path-width
• On minimizing width in linear layouts
• Interval graphs and searching
• Graph minors. X: Obstructions to tree-decomposition
• Quickly excluding a forest
• The vertex separation number of a graph equals its path-width
• Graph searching and a min-max theorem for tree-width
• Call routing and the ratcatcher
• The vertex separation and search number of a graph
• Fugitive-search games on graphs and related parameters
• Algorithms and obstructions for linear-width and related search parameters
• Searching and pebbling
• The congestion of \(n\)-cube layout on a rectangular grid
• Graph Searching and Interval Completion
• The complexity of searching a graph
• A Sufficient Condition for Backtrack-Free Search
• The bandwidth problem for graphs and matrices—a survey
• Monotonicity in graph searching
• The Linkage of a Graph
• Recontamination does not help to search a graph

This page was built for publication: On the monotonicity of games generated by symmetric submodular functions.