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)
- Monotonicity in digraph search problems
- Searching for an evader in an unknown dark cave by an optimal number of asynchronous searchers
- Graph automata for linear graph languages
- Fugitive-search games on graphs and related parameters
- Pathwidth of outerplanar graphs
- Connected graph searching in chordal graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- The search and the node-search number of dual graphs
- Resource finding in store-and-forward networks
- The searchlight problem for road networks
- A two-person game on graphs where each player tries to encircle his opponent's men
- 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
- Bounding the search number of graph products
- Searching by heterogeneous agents
- The complexity of zero-visibility cops and robber
- Integer programming models and algorithms for the graph decontamination problem with mobile agents
- How to survive while visiting a graph
- A property of random walks on a cycle graph
- Computing the one-visibility copnumber of trees
- Complexity of searching an immobile hider in a graph
- Standard directed search strategies and their applications
- The complexity of the positive semidefinite zero forcing
- The fast search number of a complete \(k\)-partite graph
- Title not available (Why is that?)
- Title not available (Why is that?)
- The theory of guaranteed search on graphs
- DECONTAMINATING CHORDAL RINGS AND TORI USING MOBILE AGENTS
- Improved self-reduction algorithms for graphs with bounded treewidth
- Unbounded search and recursive graph problems
- Contiguous search problem in Sierpiński graphs
- One-visibility cops and robber on trees: optimal cop-win strategies
- Graph searching on chordal graphs
- Single step graph search problem
- Solving the single step graph searching problem by solving the maximum two-independent set problem
- Search and sweep numbers of finite directed acyclic graphs
- Finite graph automata for linear and boundary graph languages
- The summation and bottleneck minimization for single-step searching on weighted graphs
- Distributed protocols against mobile eavesdroppers
- A frame architecture for a certain class of graph search problems
- Pathwidth is NP-Hard for Weighted Trees
- On Submodular Search and Machine Scheduling
- BOUNDARY-OPTIMAL TRIANGULATION FLOODING
- 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
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)
