Maximum vertex occupation time and inert fugitive: Recontamination does help

DOI10.1016/J.IPL.2008.12.022MaRDI QIDQ987778zbMATH OpenOpenAlexFDO

Authors 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

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

Abstract: Given a simple graph $G$, 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 $G$. 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.

Recommendations

• Monotonicity and inert fugitive search games
• Recontamination does not help to search a graph
• Monotonicity of Non-deterministic Graph Searching
• SOFSEM 2006: Theory and Practice of Computer Science
• Searching is not jumping.

Cites work

• scientific article; zbMATH DE number 3590298 (Why is no real title available?)
• Bandwidth and pebbling
• Fugitive-search games on graphs and related parameters
• Graph searching and a min-max theorem for tree-width
• Graph searching and interval completion
• Graph searching, elimination trees, and a generalization of bandwidth
• Interval graphs and searching
• Lower bounds on treespan
• Monotonicity and inert fugitive search games
• Monotonicity in graph searching
• Monotonicity of non-deterministic graph searching
• Recontamination does not help to search a graph
• Searching and pebbling

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)