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
- 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?)
- 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
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)
