Monotonicity in digraph search problems
DOI10.1016/J.TCS.2008.08.025zbMATH Open1153.68041OpenAlexW2074771880MaRDI QIDQ955030FDOQ955030
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
Recommendations
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)
Cites Work
- Depth-First Search and Linear Graph Algorithms
- Searching and pebbling
- Directed tree-width
- Directed path-width and monotonicity in digraph searching
- Introducing directed tree width
- Mathematical Foundations of Computer Science 2005
- An annotated bibliography on guaranteed graph searching
- The complexity of searching a graph
- Recontamination does not help to search a graph
- On the monotonicity of games generated by symmetric submodular functions.
- On the Monotonicity of Weak Searching
- Monotonicity in graph searching
- Searching is not jumping.
- Digraph searching, directed vertex separation and directed pathwidth
- Searching and sweeping graphs: a brief survey
- On a pursuit game on Cayley digraphs
- Search and sweep numbers of finite directed acyclic graphs
- Arc Searching Digraphs Without Jumping
- Directed one-trees
- Monotonicity of strong searching on digraphs
Cited In (13)
- On the Monotonicity of Weak Searching
- The zero-visibility cops and robber game on graph products
- On the monotonicity of process number
- Digraph Decompositions and Monotonicity in Digraph Searching
- Monotonicity of strong searching on digraphs
- Monotonicity of Non-deterministic Graph Searching
- Digraph Strong Searching: Monotonicity and Complexity
- Monotonicity of non-deterministic graph searching
- Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth
- Digraph decompositions and monotonicity in digraph searching
- Directed Searching Digraphs: Monotonicity and Complexity
- On the Cooperative Graph Searching Problem
- A simple method for proving lower bounds in the zero-visibility cops and robber game
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)
