Monotonicity in digraph search problems

DOI10.1016/J.TCS.2008.08.025MaRDI QIDQ955030zbMATH OpenOpenAlexFDO

Authors Boting Yang, Yi Cao

Publication date 18 November 2008

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

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

zbMATH Keywords

monotonicityNP-completenesspursuit-and-evasion problemdigraph searching

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)

Recommendations

• Directed Searching Digraphs: Monotonicity and Complexity
• Monotonicity of strong searching on digraphs
• Digraph Strong Searching: Monotonicity and Complexity
• On the Monotonicity of Weak Searching
• Digraph Decompositions and Monotonicity in Digraph Searching

Cites work

• An annotated bibliography on guaranteed graph searching
• Arc Searching Digraphs Without Jumping
• Depth-First Search and Linear Graph Algorithms
• Digraph searching, directed vertex separation and directed pathwidth
• Directed one-trees
• Directed path-width and monotonicity in digraph searching
• Directed tree-width
• Introducing directed tree width
• Mathematical Foundations of Computer Science 2005
• Monotonicity in graph searching
• Monotonicity of strong searching on digraphs
• On a pursuit game on Cayley digraphs
• On the Monotonicity of Weak Searching
• On the monotonicity of games generated by symmetric submodular functions.
• Recontamination does not help to search a graph
• Search and sweep numbers of finite directed acyclic graphs
• Searching and pebbling
• Searching and sweeping graphs: a brief survey
• Searching is not jumping.
• The complexity of searching a graph

Cited in

(13)

• Monotonicity of Non-deterministic Graph Searching
• Digraph Strong Searching: Monotonicity and Complexity
• A simple method for proving lower bounds in the zero-visibility cops and robber game
• Digraph Decompositions and Monotonicity in Digraph Searching
• On the Monotonicity of Weak Searching
• Monotonicity of non-deterministic graph searching
• On the Cooperative Graph Searching Problem
• Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth
• Directed Searching Digraphs: Monotonicity and Complexity
• Monotonicity of strong searching on digraphs
• The zero-visibility cops and robber game on graph products
• On the monotonicity of process number
• Digraph decompositions and monotonicity in digraph searching

This page was built for publication: Monotonicity in digraph search problems

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