Maximum vertex occupation time and inert fugitive: Recontamination does help

DOI10.1016/j.ipl.2008.12.022zbMath1197.68057arXiv0802.3512OpenAlexW2156615974MaRDI QIDQ987778

Dariusz Dereniowski

Publication date: 16 August 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0802.3512

zbMATH Keywords

combinatorial problemsinert fugitivemonotone searchnode searchrecontamination

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Searching by heterogeneous agents

Cites Work

• Unnamed Item
• Unnamed Item
• Monotonicity of non-deterministic graph searching
• Lower bounds on treespan
• Interval graphs and searching
• Graph searching and a min-max theorem for tree-width
• Fugitive-search games on graphs and related parameters
• Graph searching, elimination trees, and a generalization of bandwidth
• Searching and pebbling
• Bandwidth and pebbling
• Graph Searching and Interval Completion
• Monotonicity in graph searching
• Recontamination does not help to search a graph