Monotonicity of non-deterministic graph searching

DOI10.1016/j.tcs.2008.02.036zbMath1146.68060OpenAlexW2034927865MaRDI QIDQ930888

Nicolas Nisse, Frédéric Mazoit

Publication date: 24 June 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.02.036

zbMATH Keywords

monotonicitytreewidthgraph searching

Mathematics Subject Classification ID

Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (9)

On the monotonicity of process number ⋮ Digraph Decompositions and Monotonicity in Digraph Searching ⋮ Jumping robbers in digraphs ⋮ Edge Search Number of Cographs in Linear Time ⋮ Edge search number of cographs ⋮ The mixed search game against an agile and visible fugitive is monotone ⋮ Digraph decompositions and monotonicity in digraph searching ⋮ Maximum vertex occupation time and inert fugitive: Recontamination does help ⋮ Non-deterministic graph searching in trees

Cites Work

• Unnamed Item
• 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
• Complexity of Finding Embeddings in a k-Tree
• 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

This page was built for publication: Monotonicity of non-deterministic graph searching