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

digraph searchingmonotonicityNP-completenesspursuit-and-evasion problem

Mathematics Subject Classification ID

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

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 games generated by symmetric submodular functions.
• On the Monotonicity of Weak Searching
• 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)

• A simple method for proving lower bounds in the zero-visibility cops and robber game
• Monotonicity of strong searching on digraphs
• On the monotonicity of process number
• Monotonicity of Non-deterministic Graph Searching
• On the Monotonicity of Weak Searching
• On the Cooperative Graph Searching Problem
• 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
• Digraph Strong Searching: Monotonicity and Complexity
• Digraph decompositions and monotonicity in digraph searching
• The zero-visibility cops and robber game on graph products
• Monotonicity of non-deterministic graph 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)