Monotonicity in graph searching
From MaRDI portal
Publication:3974370
DOI10.1016/0196-6774(91)90003-HzbMATH Open0760.05081MaRDI QIDQ3974370FDOQ3974370
Authors: Daniel Bienstock, Paul Seymour 
Publication date: 25 June 1992
Published in: Journal of Algorithms (Search for Journal in Brave)
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Search theory (90B40)
Cited In (99)
- On minimum cost edge searching
- Fast-mixed searching and related problems on graphs
- Fast searching games on graphs
- Searching for an evader in an unknown dark cave by an optimal number of asynchronous searchers
- Non-deterministic graph searching in trees
- Fast edge searching and fast searching on graphs
- A polynomial time algorithm to compute the connected treewidth of a series-parallel graph
- Connected graph searching in chordal graphs
- The cost of monotonicity in distributed graph searching
- Edge Search Number of Cographs in Linear Time
- LIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depth
- Edge search number of cographs
- A 3-approximation for the pathwidth of Halin graphs
- An annotated bibliography on guaranteed graph searching
- Graph searching with advice
- Searching for a Visible, Lazy Fugitive
- Mixed searching and proper-path-width
- Decontamination of hypercubes by mobile agents
- A linear fixed parameter tractable algorithm for connected pathwidth
- Searching with mobile agents in networks with liars.
- Contraction obstructions for connected graph searching
- On the monotonicity of process number
- Fast searching on Cartesian products of graphs
- Digraph Decompositions and Monotonicity in Digraph Searching
- Graph Searching in a Crime Wave
- Monotonicity of Non-deterministic Graph Searching
- Digraph Strong Searching: Monotonicity and Complexity
- Edge searching weighted graphs
- Searching by heterogeneous agents
- On the domination search number
- Directed tree-width
- Visibility-based pursuit-evasion in a polygonal environment
- Edge and node searching problems on trees
- Connected graph searching
- The complexity of zero-visibility cops and robber
- Three-fast-searchable graphs
- Network decontamination under \(m\)-immunity
- Strong-mixed searching and pathwidth
- Quickly excluding a forest
- Monotonicity of non-deterministic graph searching
- LIFO-search on digraphs: a searching game for cycle-rank
- Digraph searching, directed vertex separation and directed pathwidth
- Monotony properties of connected visible graph searching
- Sweeping graphs with large clique number
- Fast searching on cactus graphs
- Complexity of searching an immobile hider in a graph
- On the complexity of the positive semidefinite zero forcing number
- Fugitive-search games on graphs and related parameters
- On the monotonicity of games generated by symmetric submodular functions.
- Directed path-width and monotonicity in digraph searching
- Algorithms and obstructions for linear-width and related search parameters
- Mixed search number and linear-width of interval and split graphs
- The complexity of the positive semidefinite zero forcing
- Network decontamination with temporal immunity by cellular automata
- Node-searching problem on block graphs
- Jumping robbers in digraphs
- More agents may decrease global work: a case in butterfly decontamination
- Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth
- Digraph decompositions and monotonicity in digraph searching
- The complexity of minimum-length path decompositions
- Computing on rings by oblivious robots: a unified approach for different tasks
- Positive semidefinite zero forcing: complexity and lower bounds
- Distributed chasing of network intruders
- Contiguous search problem in Sierpiński graphs
- On the Capture Time of Cops and Robbers Game on a Planar Graph
- Mixed Search Number of Permutation Graphs
- Mixed Search Number and Linear-Width of Interval and Split Graphs
- A simple method for proving lower bounds in the zero-visibility cops and robber game
- Recognizing hyperelliptic graphs in polynomial time
- Lower bounds for positive semidefinite zero forcing and their applications
- Zero-visibility cops and robber and the pathwidth of a graph
- Exclusive graph searching
- Pathwidth is NP-Hard for Weighted Trees
- Exclusive graph searching vs. pathwidth
- NETWORK DECONTAMINATION IN PRESENCE OF LOCAL IMMUNITY
- The fast search number of a Cartesian product of graphs
- Monotonicity in digraph search problems
- Graph automata for linear graph languages
- Fugitive-search games on graphs and related parameters
- Searching expenditure and interval graphs
- The zero-visibility cops and robber game on graph products
- The localization capture time of a graph
- Maximum vertex occupation time and inert fugitive: Recontamination does help
- Searching for an intruder on graphs and their subdivisions
- The capture time of a planar graph
- Four-searchable biconnected outerplanar graphs
- The mixed search game against an agile and visible fugitive is monotone
- Monotonicity of strong searching on digraphs
- Integer programming models and algorithms for the graph decontamination problem with mobile agents
- Minimum rank and zero forcing number for butterfly networks
- Combinatorial trace method for network immunization
- Throttling processes equivalent to full throttling on trees
- When is a network epidemic hard to eliminate?
- Connected search for a lazy robber
- Graph searching on chordal graphs
- Finite graph automata for linear and boundary graph languages
- Digraphs of bounded width
- Constrained graph searching on trees
- Edge searching and fast searching with constraints
This page was built for publication: Monotonicity in graph searching
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3974370)
