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