Maximum vertex occupation time and inert fugitive: Recontamination does help
From MaRDI portal
Publication:987778
DOI10.1016/J.IPL.2008.12.022zbMATH Open1197.68057arXiv0802.3512OpenAlexW2156615974MaRDI QIDQ987778FDOQ987778
Authors: Dariusz Dereniowski 
Publication date: 16 August 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Abstract: Given a simple graph , we consider the node search problem with inert fugitive. We are interested in minimizing the maximum vertex occupation time, i.e. the maximum number of steps in which a vertex is occupied by a searcher during a search of . We prove that a search program which does not allow a recontamination may not find an optimal solution to this problem, and the difference between the maximum vertex occupation time computed by a monotone search program and a program without such restriction may be arbitrarily large.
Full work available at URL: https://arxiv.org/abs/0802.3512
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Graph searching and a min-max theorem for tree-width
- Searching and pebbling
- Title not available (Why is that?)
- Recontamination does not help to search a graph
- Fugitive-search games on graphs and related parameters
- Monotonicity in graph searching
- Monotonicity of non-deterministic graph searching
- Interval graphs and searching
- Graph searching, elimination trees, and a generalization of bandwidth
- Graph searching and interval completion
- Lower bounds on treespan
- Bandwidth and pebbling
- Monotonicity and inert fugitive search games
This page was built for publication: Maximum vertex occupation time and inert fugitive: Recontamination does help
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q987778)
