scientific article; zbMATH DE number 176249
Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Structural characterization of families of graphs (05C75) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Games involving graphs (91A43)
[For the entire collection see Zbl 0753.00028.] Graph searches are best described by imagining a finite set of guards chasing a prisoner around a graph. A move consists of placing a guard at a vertex, removing a guard from a vertex, or sliding a guard along an edge. After each move the prisoner is free to move instantaneously along any path in the graph that avoids the guards. The goal is to find an efficient search strategy which eventually captures the prisoner, more specifically, to do so with the fewest number of guards. This mimimum number is called the search number of the graph. In general, finding the search number of a graph is NP-hard. Variations on this basic search game include node-searching and \(t\)-searching. In this paper the author surveys connections between various search games and graph parameters such as interval width, tree-width, and path-width. These parameters measure how closely the graph resembles a tree or path. They play a central role in the recent work on graph minors. The author discusses how ideas from the graph minor research lead to a short proof of monotonicity in mixed searching.
- Graph searching with advice
- Nondeterministic graph searching: from pathwidth to treewidth
- A partial k-arboretum of graphs with bounded treewidth
- Graph searching and a min-max theorem for tree-width
- Some generalizations of the problem on the search number of a graph
- Fugitive-search games on graphs and related parameters
- Helicopter search problems, bandwidth and pathwidth
- On the monotonicity of games generated by symmetric submodular functions.
- Edge and node searching problems on trees
- Algorithms and obstructions for linear-width and related search parameters
- Localization game on geometric and planar graphs
- How many lions are needed to clear a grid?
- Finite graph automata for linear and boundary graph languages
- The fast search number of a complete \(k\)-partite graph
- On the domination search number
- Triangulating graphs without asteroidal triples
- Approximate search strategies for weighted trees
- Edge degeneracy: algorithmic and structural results
- The cost of monotonicity in distributed graph searching
- Minimum rank and zero forcing number for butterfly networks
- Monotonicity of strong searching on digraphs
- The theory of guaranteed search on graphs
- Node-searching problem on block graphs
- Lower bounds on the pathwidth of some grid-like graphs
- On the interval completion of chordal graphs
- Directed path-width and monotonicity in digraph searching
- Fast searching on cactus graphs
- A min-max theorem for LIFO-search
- Fast searching on complete k-partite graphs
- Fast searching on Cartesian products of graphs
- From pathwidth to connected pathwidth
- Pathwidth and searching in parameterized threshold graphs
- Mixed Search Number of Permutation Graphs
- Mixed Search Number and Linear-Width of Interval and Split Graphs
- Monotony Properties of Connected Visible Graph Searching
- Fast searching games on graphs
- Edge search number of cographs
- Searching expenditure and interval graphs
- From pathwidth to connected pathwidth
- The complexity of minimum-length path decompositions
- A linear fixed parameter tractable algorithm for connected pathwidth
- scientific article; zbMATH DE number 7236450 (Why is no real title available?)
- Exclusive graph searching
- Experimental evaluation of a branch-and-bound algorithm for computing pathwidth and directed pathwidth
- The fast search number of a Cartesian product of graphs
- Searching for a Visible, Lazy Fugitive
- Computing small search numbers in linear time
- Edge Search Number of Cographs in Linear Time
- Mathematical Foundations of Computer Science 2005
- Slightly superexponential parameterized problems
- SOFSEM 2006: Theory and Practice of Computer Science
- A 3-approximation for the pathwidth of Halin graphs
- Searching is not jumping.
- Using a hybrid of exact and genetic algorithms to design survivable networks
- Connected search for a lazy robber
- Fast searching on k-combinable graphs
- Edge searching and fast searching with constraints
- Fugitive-search games on graphs and related parameters
- Constrained graph searching on trees
- Centroidal localization game
- Mixed searching and proper-path-width
- Graph parameters, universal obstructions, and WQO
- Connected graph searching
- LIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depth
- Monotonicity of the cops and robber game for bounded depth treewidth
- Exclusive graph searching vs. pathwidth
- Going deep and going wide: counting logic and homomorphism indistinguishability over graphs of bounded treedepth and treewidth
- Strong-mixed searching and pathwidth
- Network decontamination under m-immunity
- Monotonicity of non-deterministic graph searching
- The role of information in the cop-robber game
- Offline variants of the ``lion and man problem: some problems and techniques for measuring crowdedness and for safe path planning
- An annotated bibliography on guaranteed graph searching
- Distributed chasing of network intruders
- Digraph searching, directed vertex separation and directed pathwidth
- Connected graph searching in chordal graphs
- Monotony properties of connected visible graph searching
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4035355)
