The complexity of searching a graph
From MaRDI portal
Publication:3777477
Recommendations
- The complexity of searching succinctly represented graphs
- Search problems on graphs
- SOFSEM 2006: Theory and Practice of Computer Science
- The complexity of searching implicit graphs
- scientific article; zbMATH DE number 1538872
- scientific article; zbMATH DE number 15129
- Computational complexity of graphs
- On Graph Complexity
- On the optimality of a simple strategy for searching graphs
Cited in
(only showing first 100 items - show all)- Pathwidth is NP-Hard for Weighted Trees
- Fast-mixed searching and related problems on graphs
- Monotonicity in digraph search problems
- Fast searching games on graphs
- Searching for an evader in an unknown dark cave by an optimal number of asynchronous searchers
- scientific article; zbMATH DE number 4002142 (Why is no real title available?)
- On Submodular Search and Machine Scheduling
- BOUNDARY-OPTIMAL TRIANGULATION FLOODING
- Pathwidth of Circular-Arc Graphs
- Graph automata for linear graph languages
- Non-deterministic graph searching in trees
- Fast edge searching and fast searching on graphs
- The complexity of pursuit on a graph
- Search in graphs
- Distributed graph searching with a sense of direction
- Pathwidth of outerplanar graphs
- Fugitive-search games on graphs and related parameters
- Searching expenditure and interval graphs
- Connected graph searching in chordal graphs
- The zero-visibility cops and robber game on graph products
- The cost of monotonicity in distributed graph searching
- A polynomial algorithm for recognizing bounded cutwidth in hypergraphs
- Fast searching on \(k\)-combinable graphs
- Edge search number of cographs
- scientific article; zbMATH DE number 33703 (Why is no real title available?)
- On-line search in two-dimensional environment
- Edge Search Number of Cographs in Linear Time
- scientific article; zbMATH DE number 2220912 (Why is no real title available?)
- Search for the end of a path in the \(\cdot\)-dimensional grid and in other graphs
- Robust shortest path planning and semicontractive dynamic programming
- A 3-approximation for the pathwidth of Halin graphs
- An annotated bibliography on guaranteed graph searching
- Graph searching with advice
- Mixed searching and proper-path-width
- scientific article; zbMATH DE number 1472189 (Why is no real title available?)
- The search and the node-search number of dual graphs
- Locating a robber with multiple probes
- Complexity of node coverage games
- Resource finding in store-and-forward networks
- The searchlight problem for road networks
- Bushiness and a tight worst-case upper bound on the search number of a simple polygon.
- Four-searchable biconnected outerplanar graphs
- Network decontamination with a single agent
- Decontamination of hypercubes by mobile agents
- Searching with mobile agents in networks with liars.
- A two-person game on graphs where each player tries to encircle his opponent's men
- Minimal trees of given search number
- Fast searching on complete \(k\)-partite graphs
- Fast searching on Cartesian products of graphs
- Cooperative exploration and protection of a workspace assisted by information networks
- Monotonicity of strong searching on digraphs
- Approximate search strategies for weighted trees
- A graph search algorithm for indoor pursuit/evasion
- Monotonicity of Non-deterministic Graph Searching
- Edge searching weighted graphs
- Tradeoffs in process strategy games with application in the WDM reconfiguration problem
- Searching and pebbling
- Zero-visibility cops and robber game on cage graph
- Directed tree-width
- Bounding the search number of graph products
- Connected graph searching
- The complexity of zero-visibility cops and robber
- Edge and node searching problems on trees
- Linear rank-width and linear clique-width of trees
- How to survive while visiting a graph
- Visibility-based pursuit-evasion in a polygonal environment
- Cleaning a network with brushes
- A property of random walks on a cycle graph
- Network decontamination under m-immunity
- Parallel cleaning of a network with brushes
- Integer programming models and algorithms for the graph decontamination problem with mobile agents
- Three-fast-searchable graphs
- Strong-mixed searching and pathwidth
- Nontrivial discontinuities of the Golovach functions for trees
- Computing the one-visibility cop-win strategies for trees
- Monotonicity of non-deterministic graph searching
- Minimal trees of a given search number
- Digraph searching, directed vertex separation and directed pathwidth
- Monotony properties of connected visible graph searching
- Sweeping graphs with large clique number
- Vision-Based Pursuit-Evasion in a Grid
- A 3-approximation for the pathwidth of Halin graphs
- An NP-completeness result of edge search in graphs
- Computing the one-visibility copnumber of trees
- INTRUDER CAPTURING IN MESH AND TORUS NETWORKS
- Complexity of searching an immobile hider in a graph
- On the pathwidth of chordal graphs
- Fast searching on cactus graphs
- Standard directed search strategies and their applications
- Fugitive-search games on graphs and related parameters
- On the monotonicity of games generated by symmetric submodular functions.
- Cops and robber game without recharging
- On the complexity of the positive semidefinite zero forcing number
- 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
- The fast search number of a complete \(k\)-partite graph
- Lower and upper competitive bounds for online directed graph exploration
- More agents may decrease global work: a case in butterfly decontamination
This page was built for publication: The complexity of searching a graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3777477)
