The complexity of searching a graph
From MaRDI portal
Publication:3777477
DOI10.1145/42267.42268zbMath0637.68081OpenAlexW2154788235WikidataQ61248965 ScholiaQ61248965MaRDI QIDQ3777477
Nimrod Megiddo, S. Louis Hakimi, Michael R. Garey, Christos H. Papadimitriou, David S. Johnson
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
Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Searching for an evader in an unknown dark cave by an optimal number of asynchronous searchers, Improved self-reduction algorithms for graphs with bounded treewidth, NETWORK DECONTAMINATION IN PRESENCE OF LOCAL IMMUNITY, DECONTAMINATING CHORDAL RINGS AND TORI USING MOBILE AGENTS, Pathwidth of outerplanar graphs, Network decontamination with a single agent, Positive Semidefinite Zero Forcing: Complexity and Lower Bounds, The cost of monotonicity in distributed graph searching, On a pursuit game played on graphs for which a minor is excluded, Computing the one-visibility cop-win strategies for trees, Decontamination of hypercubes by mobile agents, Lower and upper competitive bounds for online directed graph exploration, More agents may decrease global work: a case in butterfly decontamination, Strong-mixed searching and pathwidth, Complexity of searching an immobile hider in a graph, The Complexity of the Positive Semidefinite Zero Forcing, Locating a robber with multiple probes, Approximate search strategies for weighted trees, Fast-mixed searching and related problems on graphs, Fugitive-search games on graphs and related parameters, Fast searching games on graphs, Fast Searching on Complete k-partite Graphs, Mixed Search Number of Permutation Graphs, The complexity of zero-visibility cops and robber, Edge search number of cographs, Monotonicity of Non-deterministic Graph Searching, Pathwidth of Circular-Arc Graphs, Mixed Search Number and Linear-Width of Interval and Split Graphs, Monotonicity of strong searching on digraphs, A distributed algorithm for computing the node search number in trees, Fast edge searching and fast searching on graphs, On the monotonicity of games generated by symmetric submodular functions., Network decontamination under \(m\)-immunity, Fast searching on cactus graphs, Tradeoffs in process strategy games with application in the WDM reconfiguration problem, A variation on the min cut linear arrangement problem, The theory of guaranteed search on graphs, INTRUDER CAPTURING IN MESH AND TORUS NETWORKS, Unnamed Item, Searching with mobile agents in networks with liars., Three-fast-searchable graphs, Fast Searching on Cartesian Products of Graphs, Monotonicity of non-deterministic graph searching, Cleaning a network with brushes, An annotated bibliography on guaranteed graph searching, Distributed chasing of network intruders, Capture bounds for visibility-based pursuit evasion, Single step graph search problem, One-visibility cops and robber on trees, Node-searching problem on block graphs, Digraph searching, directed vertex separation and directed pathwidth, The complexity of pursuit on a graph, Mixed searching and proper-path-width, Four-searchable biconnected outerplanar graphs, Lower bounds for positive semidefinite zero forcing and their applications, Monotonicity in digraph search problems, Escaping offline searchers and isoperimetric theorems, Cooperative exploration and protection of a workspace assisted by information networks, Exclusive graph searching, The fast search number of a Cartesian product of graphs, Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm, Connected graph searching, Cops and robber game without recharging, Search and sweep numbers of finite directed acyclic graphs, Connected graph searching in chordal graphs, Parallel cleaning of a network with brushes, A graph search algorithm for indoor pursuit/evasion, Finite graph automata for linear and boundary graph languages, Contiguous search problem in Sierpiński graphs, CSP duality and trees of bounded pathwidth, Characterization of graphs and digraphs with small process numbers, Mixed search number and linear-width of interval and split graphs, Exclusive graph searching vs. pathwidth, Monotony properties of connected visible graph searching, Computing the one-visibility copnumber of trees, The fast search number of a complete \(k\)-partite graph, A property of random walks on a cycle graph, Graph searching with advice, On minimizing width in linear layouts, Minimal trees of a given search number, Resource finding in store-and-forward networks, Edge searching weighted graphs, Searching and pebbling, Standard directed search strategies and their applications, A two-person game on graphs where each player tries to encircle his opponent's men, Edge and node searching problems on trees, One-visibility cops and robber on trees: optimal cop-win strategies, Sweeping graphs with large clique number, Algorithms and obstructions for linear-width and related search parameters, Robust shortest path planning and semicontractive dynamic programming, Directed tree-width, On the pathwidth of chordal graphs, The summation and bottleneck minimization for single-step searching on weighted graphs, Complexity of node coverage games, Bushiness and a tight worst-case upper bound on the search number of a simple polygon., Non-deterministic graph searching in trees, Linear rank-width and linear clique-width of trees, Searching expenditure and interval graphs, The searchlight problem for road networks, Distributed graph searching with a sense of direction, Bounding the search number of graph products, Edge Search Number of Cographs in Linear Time, Pathwidth is NP-Hard for Weighted Trees, Integer programming models and algorithms for the graph decontamination problem with mobile agents, Visibility-based pursuit-evasion in a polygonal environment, Distributed protocols against mobile eavesdroppers, Fast searching on \(k\)-combinable graphs, On Submodular Search and Machine Scheduling, Edge searching and fast searching with constraints, Graph automata for linear graph languages, A 3-approximation for the pathwidth of Halin graphs, A 3-approximation for the pathwidth of Halin graphs, Fugitive-search games on graphs and related parameters, Network Decontamination with Temporal Immunity by Cellular Automata, A polynomial algorithm for recognizing bounded cutwidth in hypergraphs, On-line search in two-dimensional environment, On the complexity of the positive semidefinite zero forcing number, Searching by heterogeneous agents, BOUNDARY-OPTIMAL TRIANGULATION FLOODING, Vision-Based Pursuit-Evasion in a Grid, Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth
