The complexity of searching a graph
From MaRDI portal
Publication:3777477
DOI10.1145/42267.42268zbMATH Open0637.68081DBLPjournals/jacm/MegiddoHGJP88OpenAlexW2154788235WikidataQ61248965 ScholiaQ61248965MaRDI QIDQ3777477FDOQ3777477
Authors: Nimrod Megiddo, S. Louis Hakimi, M. R. Garey, D. S. Johnson, Christos Papadimitriou 
Publication date: 1988
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/42267.42268
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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Searching and sorting (68P10)
Cited In (only showing first 100 items - show all)
- Fast-mixed searching and related problems on graphs
- Fast searching games on graphs
- Pathwidth of Circular-Arc Graphs
- Non-deterministic graph searching in trees
- Search in graphs
- Fast edge searching and fast searching on graphs
- The complexity of pursuit on a graph
- A polynomial algorithm for recognizing bounded cutwidth in hypergraphs
- The cost of monotonicity in distributed graph searching
- Fast searching on \(k\)-combinable graphs
- Edge Search Number of Cographs in Linear Time
- Edge search number of cographs
- Title not available (Why is that?)
- A 3-approximation for the pathwidth of Halin graphs
- Robust shortest path planning and semicontractive dynamic programming
- An annotated bibliography on guaranteed graph searching
- Graph searching with advice
- Mixed searching and proper-path-width
- Locating a robber with multiple probes
- Bushiness and a tight worst-case upper bound on the search number of a simple polygon.
- Decontamination of hypercubes by mobile agents
- Network decontamination with a single agent
- Searching with mobile agents in networks with liars.
- Fast searching on complete \(k\)-partite graphs
- Fast searching on Cartesian products of graphs
- Minimal trees of given search number
- Searching and pebbling
- Tradeoffs in process strategy games with application in the WDM reconfiguration problem
- Directed tree-width
- Visibility-based pursuit-evasion in a polygonal environment
- Linear rank-width and linear clique-width of trees
- Edge and node searching problems on trees
- Connected graph searching
- Cleaning a network with brushes
- Three-fast-searchable graphs
- Network decontamination under \(m\)-immunity
- Parallel cleaning of a network with brushes
- Nontrivial discontinuities of the Golovach functions for trees
- Strong-mixed searching and pathwidth
- Minimal trees of a given search number
- Monotonicity of non-deterministic graph searching
- Vision-Based Pursuit-Evasion in a Grid
- Digraph searching, directed vertex separation and directed pathwidth
- Monotony properties of connected visible graph searching
- Sweeping graphs with large clique number
- An NP-completeness result of edge search in graphs
- Fast searching on cactus graphs
- On the pathwidth of chordal graphs
- 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.
- Cops and robber game without recharging
- Algorithms and obstructions for linear-width and related search parameters
- Mixed search number and linear-width of interval and split graphs
- Network decontamination with temporal immunity by cellular automata
- Node-searching problem on block graphs
- Lower and upper competitive bounds for online directed graph exploration
- 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
- Capture bounds for visibility-based pursuit evasion
- On minimizing width in linear layouts
- A variation on the min cut linear arrangement problem
- Escaping offline searchers and isoperimetric theorems
- Characterization of graphs and digraphs with small process numbers
- Positive semidefinite zero forcing: complexity and lower bounds
- Distributed chasing of network intruders
- Title not available (Why is that?)
- SOFSEM 2006: Theory and Practice of Computer Science
- A distributed algorithm for computing the node search number in trees
- Mixed Search Number of Permutation Graphs
- Mixed Search Number and Linear-Width of Interval and Split Graphs
- Lower Bounds on Edge Searching
- Searching Cycle-Disjoint Graphs
- CSP duality and trees of bounded pathwidth
- Lower bounds for positive semidefinite zero forcing and their applications
- On a pursuit game played on graphs for which a minor is excluded
- Title not available (Why is that?)
- Exclusive graph searching
- Exclusive graph searching vs. pathwidth
- NETWORK DECONTAMINATION IN PRESENCE OF LOCAL IMMUNITY
- The fast search number of a Cartesian product of graphs
- Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm
- Searching expenditure and interval graphs
- Distributed graph searching with a sense of direction
- The zero-visibility cops and robber game on graph products
- On-line search in two-dimensional environment
- Search for the end of a path in the \(\cdot\)-dimensional grid and in other graphs
- Complexity of node coverage games
- Four-searchable biconnected outerplanar graphs
- Cooperative exploration and protection of a workspace assisted by information networks
- Zero-visibility cops and robber game on cage graph
- Computing the one-visibility cop-win strategies for trees
- A 3-approximation for the pathwidth of Halin graphs
- INTRUDER CAPTURING IN MESH AND TORUS NETWORKS
- On the Cooperative Graph Searching Problem
- The complexity of growing a graph
- Constrained graph searching on trees
- One-visibility cops and robber on trees
- Edge searching and fast searching with constraints
- Title not available (Why is that?)
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)
