Searching and pebbling

DOI10.1016/0304-3975(86)90146-5zbMath0616.68064OpenAlexW2015469394WikidataQ29030357 ScholiaQ29030357MaRDI QIDQ1821562

Lefteris M. Kirousis, Christos H. Papadimitriou

Publication date: 1986

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(86)90146-5

zbMATH Keywords

NP-completeness directed acyclic graph undirected graph vertex separator pebble games node-search number games played on graphs graph-searching games layout parameters of a graph progressive node search number progressive pebble demand number

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20)

Related Items

Bounding the search number of graph products, Memory requirements for table computations in partial k-tree algorithms, The pathwidth and treewidth of cographs, A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth, Edge Search Number of Cographs in Linear Time, Pathwidth is NP-Hard for Weighted Trees, Order Reconfiguration under Width Constraints, Connected search for a lazy robber, Optimizing concurrency under Scheduling by Edge Reversal, Unnamed Item, Fugitive-search games on graphs and related parameters, On the complexity of the positive semidefinite zero forcing number, Vision-Based Pursuit-Evasion in a Grid, Experimental Evaluation of a Branch-and-Bound Algorithm for Computing Pathwidth and Directed Pathwidth, Complexity and monotonicity results for domination games, Searching for an evader in an unknown dark cave by an optimal number of asynchronous searchers, Intruder alert! Optimization models for solving the mobile robot graph-clear problem, Improved self-reduction algorithms for graphs with bounded treewidth, A polynomial time algorithm to compute the connected treewidth of a series-parallel graph, NETWORK DECONTAMINATION IN PRESENCE OF LOCAL IMMUNITY, DECONTAMINATING CHORDAL RINGS AND TORI USING MOBILE AGENTS, Finding hidden independent sets in interval graphs, On the monotonicity of process number, Decontamination of hypercubes by mobile agents, Combining intensification and diversification strategies in VNS. An application to the vertex separation problem, A simple method for proving lower bounds in the zero-visibility cops and robber game, Variable neighborhood search for the vertex separation problem, Jumping robbers in digraphs, Min Cut is NP-complete for edge weighted trees, Strong-mixed searching and pathwidth, Computing the vertex separation of unicyclic graphs, The Complexity of the Positive Semidefinite Zero Forcing, On minimum cost edge searching, Approximate search strategies for weighted trees, Fast-mixed searching and related problems on graphs, Fugitive-search games on graphs and related parameters, Helicopter search problems, bandwidth and pathwidth, How to hunt an invisible rabbit on a graph, Fast searching games on 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, The mixed search game against an agile and visible fugitive is monotone, Monotonicity of strong searching on digraphs, Connections between cutting-pattern sequencing, VLSI design, and flexible machines, 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, The dag-width of directed graphs, The theory of guaranteed search on graphs, INTRUDER CAPTURING IN MESH AND TORUS NETWORKS, Unnamed Item, Unnamed Item, Three-fast-searchable graphs, Fast Searching on Cartesian Products of Graphs, Monotonicity of non-deterministic graph searching, An annotated bibliography on guaranteed graph searching, Distributed chasing of network intruders, Approximation algorithms for digraph width parameters, Unnamed Item, Quickly excluding a forest, The complexity of minimum-length path decompositions, Node-searching problem on block graphs, Narrowness, pathwidth, and their application in natural language processing, Digraph searching, directed vertex separation and directed pathwidth, ON mRJ REACHABILITY IN TREES, Mixed searching and proper-path-width, Lower bounds for positive semidefinite zero forcing and their applications, Monotonicity in digraph search problems, The vertex separation number of a graph equals its path-width, Exclusive graph searching, Lower bounds on the pathwidth of some grid-like graphs, The fast search number of a Cartesian product of graphs, Connected graph searching, On tradeoffs between width- and fill-like graph parameters, Step-wise tile assembly with a constant number of tile types, Search and sweep numbers of finite directed acyclic graphs, Connected graph searching in chordal graphs, A graph search algorithm for indoor pursuit/evasion, Finite graph automata for linear and boundary graph languages, The treewidth of proofs, LIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depth, Contiguous search problem in Sierpiński graphs, CSP duality and trees of bounded pathwidth, Maximum vertex occupation time and inert fugitive: Recontamination does help, Connected searching of weighted trees, On reachability in graphs with obstacles, Exclusive graph searching vs. pathwidth, Monotony properties of connected visible graph searching, A property of random walks on a cycle graph, On the domination search number, LIFO-Search on Digraphs: A Searching Game for Cycle-Rank, Nondeterministic graph searching: from pathwidth to treewidth, Edge searching weighted graphs, A partial k-arboretum of graphs with bounded treewidth, Standard directed search strategies and their applications, A two-person game on graphs where each player tries to encircle his opponent's men, On Rerouting Connection Requests in Networks with Shared Bandwidth, Edge and node searching problems on trees, One-visibility cops and robber on trees: optimal cop-win strategies, Finding small-width connected path decompositions in polynomial time, Sweeping graphs with large clique number, Computing the chromatic number using graph decompositions via matrix rank, Algorithms and obstructions for linear-width and related search parameters, Directed tree-width, Interval graphs and searching, On the pathwidth of chordal graphs, Linear rank-width and linear clique-width of trees, Searching expenditure and interval graphs, The searchlight problem for road networks

Cites Work