Monotonicity of non-deterministic graph searching

DOI10.1016/J.TCS.2008.02.036MaRDI QIDQ930888zbMATHOpenAlexFDO

Authors Frédéric Mazoit, Nicolas Nisse

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

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

Recommendations

• Monotonicity of Non-deterministic Graph Searching
• Monotonicity in digraph search problems
• Monotonicity and inert fugitive search games
• Non-deterministic graph searching in trees
• On the Monotonicity of Weak Searching

Cites work

• scientific article; zbMATH DE number 176249 (Why is no real title available?)
• scientific article; zbMATH DE number 3590298 (Why is no real title available?)
• Algorithms and Computation
• Complexity of Finding Embeddings in a k-Tree
• DAG-Width and Parity Games
• DAG-width
• Directed path-width and monotonicity in digraph searching
• Directed tree-width
• Fugitive-search games on graphs and related parameters
• Graph minors. II. Algorithmic aspects of tree-width
• Graph minors. X: Obstructions to tree-decomposition
• Graph searching and a min-max theorem for tree-width
• Mathematical Foundations of Computer Science 2005
• Monotonicity in graph searching
• Monotony Properties of Connected Visible Graph Searching
• Recontamination does not help to search a graph
• Searching and pebbling
• The complexity of searching a graph
• The vertex separation and search number of a graph

Cited in

(13)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q930888)