Monotonicity of Non-deterministic Graph Searching

DOI10.1007/978-3-540-74839-7_4zbMath1141.68543MaRDI QIDQ3508552

Nicolas Nisse, Frédéric Mazoit

Publication date: 1 July 2008

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-74839-7_4

zbMATH Keywords

Monotonicity; Treewidth; Graph searching

Mathematics Subject Classification ID

91A43: Games involving graphs

68R10: Graph theory (including graph drawing) in computer science

Related Items

Digraph Decompositions and Monotonicity in Digraph Searching, An annotated bibliography on guaranteed graph searching, Nondeterministic graph searching: from pathwidth to treewidth

Cites Work

• Unnamed Item
• Graph minors. X: Obstructions to tree-decomposition
• Graph searching and a min-max theorem for tree-width
• The vertex separation and search number of a graph
• Fugitive-search games on graphs and related parameters
• Searching and pebbling
• Directed tree-width
• Directed path-width and monotonicity in digraph searching
• Monotony Properties of Connected Visible Graph Searching
• DAG-width
• Graph minors. II. Algorithmic aspects of tree-width
• The complexity of searching a graph
• Monotonicity in graph searching
• Recontamination does not help to search a graph
• DAG-Width and Parity Games
• Mathematical Foundations of Computer Science 2005
• Algorithms and Computation