Recontamination does not help to search a graph
From MaRDI portal
Publication:5286162
DOI10.1145/151261.151263zbMath0768.68048OpenAlexW1998007106MaRDI QIDQ5286162
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
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (93)
Searching for an evader in an unknown dark cave by an optimal number of asynchronous searchers ⋮ Improved self-reduction algorithms for graphs with bounded treewidth ⋮ NETWORK DECONTAMINATION IN PRESENCE OF LOCAL IMMUNITY ⋮ DECONTAMINATING CHORDAL RINGS AND TORI USING MOBILE AGENTS ⋮ Network decontamination with a single agent ⋮ Contraction obstructions for connected graph searching ⋮ On the monotonicity of process number ⋮ The capture time of a planar graph ⋮ The cost of monotonicity in distributed graph searching ⋮ On the Cooperative Graph Searching Problem ⋮ Digraph Decompositions and Monotonicity in Digraph Searching ⋮ Decontamination of hypercubes by mobile agents ⋮ Searching for an intruder on graphs and their subdivisions ⋮ More agents may decrease global work: a case in butterfly decontamination ⋮ Min Cut is NP-complete for edge weighted trees ⋮ Strong-mixed searching and pathwidth ⋮ How many lions are needed to clear a grid? ⋮ Edge Search Number of Cographs in Linear Time ⋮ Pathwidth is NP-Hard for Weighted Trees ⋮ Computing the vertex separation of unicyclic graphs ⋮ Integer programming models and algorithms for the graph decontamination problem with mobile agents ⋮ A robber locating strategy for trees ⋮ Locating a robber with multiple probes ⋮ On minimum cost edge searching ⋮ Approximate search strategies for weighted trees ⋮ Visibility-based pursuit-evasion in a polygonal environment ⋮ Fast-mixed searching and related problems on graphs ⋮ Fugitive-search games on graphs and related parameters ⋮ Helicopter search problems, bandwidth and pathwidth ⋮ Lions and contamination: monotone clearings ⋮ Connected search for a lazy robber ⋮ Fast searching games on graphs ⋮ On the Capture Time of Cops and Robbers Game on a Planar Graph ⋮ Edge searching and fast searching with constraints ⋮ Mixed Search Number of Permutation Graphs ⋮ Edge search number of cographs ⋮ Monotonicity of Non-deterministic Graph Searching ⋮ Mixed Search Number and Linear-Width of Interval and Split Graphs ⋮ Monotonicity of strong searching on digraphs ⋮ A distributed algorithm for computing the node search number in trees ⋮ Fast edge searching and fast searching on graphs ⋮ On the monotonicity of games generated by symmetric submodular functions. ⋮ Network decontamination under \(m\)-immunity ⋮ Fast searching on cactus graphs ⋮ Digraph decompositions and monotonicity in digraph searching ⋮ When Is a Network Epidemic Hard to Eliminate? ⋮ INTRUDER CAPTURING IN MESH AND TORUS NETWORKS ⋮ Three-fast-searchable graphs ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Monotonicity of non-deterministic graph searching ⋮ An annotated bibliography on guaranteed graph searching ⋮ Distributed chasing of network intruders ⋮ Quickly excluding a forest ⋮ Digraph searching, directed vertex separation and directed pathwidth ⋮ Mixed searching and proper-path-width ⋮ Graph automata for linear graph languages ⋮ Four-searchable biconnected outerplanar graphs ⋮ Parameters Related to Tree‐Width, Zero Forcing, and Maximum Nullity of a Graph ⋮ Monotonicity in digraph search problems ⋮ The vertex separation number of a graph equals its path-width ⋮ Cooperative exploration and protection of a workspace assisted by information networks ⋮ Lower bounds on the pathwidth of some grid-like graphs ⋮ Connected graph searching ⋮ On tradeoffs between width- and fill-like graph parameters ⋮ Fugitive-search games on graphs and related parameters ⋮ Connected graph searching in chordal graphs ⋮ A graph search algorithm for indoor pursuit/evasion ⋮ Finite graph automata for linear and boundary graph languages ⋮ LIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depth ⋮ Contiguous search problem in Sierpiński graphs ⋮ CSP duality and trees of bounded pathwidth ⋮ Maximum vertex occupation time and inert fugitive: Recontamination does help ⋮ Mixed search number and linear-width of interval and split graphs ⋮ Recognizing hyperelliptic graphs in polynomial time ⋮ On-line search in two-dimensional environment ⋮ Monotony properties of connected visible graph searching ⋮ A property of random walks on a cycle graph ⋮ Graph searching with advice ⋮ Searching by heterogeneous agents ⋮ On the domination search number ⋮ LIFO-Search on Digraphs: A Searching Game for Cycle-Rank ⋮ On minimizing width in linear layouts ⋮ Edge searching weighted graphs ⋮ A partial k-arboretum of graphs with bounded treewidth ⋮ Searching and pebbling ⋮ Edge and node searching problems on trees ⋮ Lions and contamination, triangular grids, and Cheeger constants ⋮ Sweeping graphs with large clique number ⋮ Directed tree-width ⋮ Zero-visibility cops and robber and the pathwidth of a graph ⋮ Complexity of node coverage games ⋮ Searching expenditure and interval graphs ⋮ The localization capture time of a graph
This page was built for publication: Recontamination does not help to search a graph
