Recontamination does not help to search a graph
From MaRDI portal
Publication:5286162
DOI10.1145/151261.151263zbMATH Open0768.68048OpenAlexW1998007106WikidataQ130987910 ScholiaQ130987910MaRDI QIDQ5286162FDOQ5286162
Authors: Andrea S. LaPaugh 
Publication date: 29 June 1993
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/151261.151263
Recommendations
- Graph searching problems with the counteraction
- scientific article; zbMATH DE number 2233648
- scientific article; zbMATH DE number 2220912
- An analysis of repeated graph search
- scientific article; zbMATH DE number 2102754
- scientific article; zbMATH DE number 1953084
- Publication:3469125
- Regular graphs are not universal fixers
- scientific article; zbMATH DE number 1538872
- Binary search in graphs revisited
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Searching and sorting (68P10)
Cited In (96)
- Monotonicity in digraph search problems
- 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
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- Fast edge searching and fast searching on graphs
- 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
- An annotated bibliography on guaranteed graph searching
- Graph searching with advice
- Mixed searching and proper-path-width
- Locating a robber with multiple probes
- Min Cut is NP-complete for edge weighted trees
- Decontamination of hypercubes by mobile agents
- A partial k-arboretum of graphs with bounded treewidth
- Network decontamination with a single agent
- A robber locating strategy for trees
- Contraction obstructions for connected graph searching
- 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
- Approximate search strategies for weighted trees
- A graph search algorithm for indoor pursuit/evasion
- Edge searching weighted graphs
- Searching by heterogeneous agents
- On the domination search number
- Searching and pebbling
- Directed tree-width
- Visibility-based pursuit-evasion in a polygonal environment
- Edge and node searching problems on trees
- Connected graph searching
- Three-fast-searchable graphs
- A property of random walks on a cycle graph
- 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
- The vertex separation number of a graph equals its path-width
- Fast searching on cactus graphs
- Fugitive-search games on graphs and related parameters
- On the monotonicity of games generated by symmetric submodular functions.
- Lower bounds on the pathwidth of some grid-like graphs
- Mixed search number and linear-width of interval and split graphs
- Computing the vertex separation of unicyclic graphs
- DECONTAMINATING CHORDAL RINGS AND TORI USING MOBILE AGENTS
- More agents may decrease global work: a case in butterfly decontamination
- On minimizing width in linear layouts
- Digraph decompositions and monotonicity in digraph searching
- Parameters related to tree-width, zero forcing, and maximum nullity of a graph
- Distributed chasing of network intruders
- Contiguous search problem in Sierpiński graphs
- A distributed algorithm for computing the node search number in trees
- 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
- CSP duality and trees of bounded pathwidth
- Recognizing hyperelliptic graphs in polynomial time
- How many lions are needed to clear a grid?
- Zero-visibility cops and robber and the pathwidth of a graph
- Helicopter search problems, bandwidth and pathwidth
- Pathwidth is NP-Hard for Weighted Trees
- NETWORK DECONTAMINATION IN PRESENCE OF LOCAL IMMUNITY
- 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
- On-line search in two-dimensional environment
- On tradeoffs between width- and fill-like graph parameters
- The localization capture time of a graph
- Maximum vertex occupation time and inert fugitive: Recontamination does help
- Complexity of node coverage games
- Searching for an intruder on graphs and their subdivisions
- The capture time of a planar graph
- Four-searchable biconnected outerplanar graphs
- Cooperative exploration and protection of a workspace assisted by information networks
- Integer programming models and algorithms for the graph decontamination problem with mobile agents
- INTRUDER CAPTURING IN MESH AND TORUS NETWORKS
- When is a network epidemic hard to eliminate?
- Improved self-reduction algorithms for graphs with bounded treewidth
- Lions and contamination: monotone clearings
- Connected search for a lazy robber
- On the Cooperative Graph Searching Problem
- Graph searching on chordal graphs
- Lions and contamination, triangular grids, and Cheeger constants
- Finite graph automata for linear and boundary graph languages
- Constrained graph searching on trees
- Edge searching and fast searching with constraints
This page was built for publication: Recontamination does not help to search a graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5286162)
