Monotony properties of connected visible graph searching

DOI10.1016/j.ic.2008.09.002zbMath1152.91383OpenAlexW2139957765MaRDI QIDQ999260

Nicolas Nisse, Pierre Fraigniaud

Publication date: 3 February 2009

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2008.09.002

zbMATH Keywords

treewidthpathwidthgraph searching

Mathematics Subject Classification ID

Games involving graphs (91A43) Graph theory (including graph drawing) in computer science (68R10)

Related Items

A polynomial time algorithm to compute the connected treewidth of a series-parallel graph ⋮ On the monotonicity of process number ⋮ The cost of monotonicity in distributed graph searching ⋮ Jumping robbers in digraphs ⋮ Combinatorial trace method for network immunization ⋮ Connected search for a lazy robber ⋮ A connected version of the graph coloring game ⋮ Connected graph searching ⋮ Step-wise tile assembly with a constant number of tile types ⋮ Searching by heterogeneous agents ⋮ Finding small-width connected path decompositions in polynomial time

Cites Work

• Unnamed Item
• An annotated bibliography on guaranteed graph searching
• A partial k-arboretum of graphs with bounded treewidth
• Graph searching and a min-max theorem for tree-width
• The vertex separation and search number of a graph
• Fugitive-search games on graphs and related parameters
• Searching and pebbling
• Monotony Properties of Connected Visible Graph Searching
• Connected Treewidth and Connected Graph Searching
• Graph minors. II. Algorithmic aspects of tree-width
• The complexity of searching a graph
• Monotonicity in graph searching
• Recontamination does not help to search a graph
• Mathematical Foundations of Computer Science 2005
• Algorithms and Computation
• Graph-Theoretic Concepts in Computer Science