Monotonicity of non-deterministic graph searching

DOI10.1016/J.TCS.2008.02.036MaRDI QIDQ930888zbMATH OpenOpenAlexFDO

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)

• Non-deterministic graph searching in trees
• Edge search number of cographs
• Edge Search Number of Cographs in Linear Time
• Maximum vertex occupation time and inert fugitive: Recontamination does help
• On the monotonicity of process number
• 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
• Monotonicity of Non-deterministic Graph Searching
• Digraph Strong Searching: Monotonicity and Complexity
• Jumping robbers in digraphs
• Digraph decompositions and monotonicity in digraph searching
• Nondeterministic graph searching: from pathwidth to treewidth

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)