Fugitive-search games on graphs and related parameters
From MaRDI portal
Publication:1392025
DOI10.1016/S0304-3975(96)00177-6zbMath0903.68052OpenAlexW2072099942MaRDI QIDQ1392025
Lefteris M. Kirousis, Dimitrios M. Thilikos, Nick D. Dendris
Publication date: 23 July 1998
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-3975(96)00177-6
Related Items
A polynomial time algorithm to compute the connected treewidth of a series-parallel graph, Contraction obstructions for connected graph searching, Digraph Decompositions and Monotonicity in Digraph Searching, Decontamination of hypercubes by mobile agents, Treewidth for graphs with small chordality, Integer programming models and algorithms for the graph decontamination problem with mobile agents, Helicopter search problems, bandwidth and pathwidth, Edge-treewidth: algorithmic and combinatorial properties, Connected search for a lazy robber, Directed elimination games, Fast searching games on graphs, Minimum rank and zero forcing number for butterfly networks, Graph Searching in a Crime Wave, Monotonicity of Non-deterministic Graph Searching, The mixed search game against an agile and visible fugitive is monotone, Monotonicity of strong searching on digraphs, On the monotonicity of games generated by symmetric submodular functions., Digraph decompositions and monotonicity in digraph searching, The dag-width of directed graphs, The theory of guaranteed search on graphs, Digraphs of bounded elimination width, On the algorithmic effectiveness of digraph decompositions and complexity measures, Time constrained graph searching, Monotonicity of non-deterministic graph searching, Digraph measures: Kelly decompositions, games, and orderings, Offline variants of the ``lion and man problem: some problems and techniques for measuring crowdedness and for safe path planning, An annotated bibliography on guaranteed graph searching, Approximation algorithms for digraph width parameters, The complexity of minimum-length path decompositions, Digraph searching, directed vertex separation and directed pathwidth, On tradeoffs between width- and fill-like graph parameters, A note on exact algorithms for vertex ordering problems on graphs, Connected graph searching in chordal graphs, Recognizing digraphs of Kelly-width 2, LIFO-search: a min-max theorem and a searching game for cycle-rank and tree-depth, Contiguous search problem in Sierpiński graphs, Maximum vertex occupation time and inert fugitive: Recontamination does help, Directed path-width and monotonicity in digraph searching, Monotony properties of connected visible graph searching, On the domination search number, LIFO-Search on Digraphs: A Searching Game for Cycle-Rank, All structured programs have small tree width and good register allocation, Nondeterministic graph searching: from pathwidth to treewidth, A partial k-arboretum of graphs with bounded treewidth, Searching for a Visible, Lazy Fugitive, Algorithms and obstructions for linear-width and related search parameters, Linear rank-width and linear clique-width of trees, Searching expenditure and interval graphs, Static search games played over graphs and general metric spaces
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Graph minors. III. Planar tree-width
- Interval graphs and searching
- Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
- Tree clustering for constraint networks
- Quickly excluding a forest
- The vertex separation number of a graph equals its path-width
- Graph searching and a min-max theorem for tree-width
- The vertex separation and search number of a graph
- Treewidth for graphs with small chordality
- Searching and pebbling
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- A sufficient condition for backtrack-bounded search
- The complexity of searching a graph
- A Sufficient Condition for Backtrack-Free Search
- Monotonicity in graph searching
- The Pathwidth and Treewidth of Cographs
- TREEWIDTH OF CIRCLE GRAPHS
- The Linkage of a Graph
- Recontamination does not help to search a graph
