ALBERT — All Library Books, journals and Electronic Records Telegrafenberg

Hits per page

hit 1 - 1 | 1 hit

Select All Export

Unknown

Algorithms, Vol. 2, Pages 1069-1086: How Many Lions Are Needed to Clear a Grid? (2011)

Florian Berger; Alexander Gilbers; Ansgar Grüne; Rolf Klein

MDPI Publishing

In: Algorithms

add to mindlist on the mindlist

Details

Publication Date: 2011-06-07

Description: We consider a pursuit-evasion problem where some lions have the task to clear a grid graph whose nodes are initially contaminated. The contamination spreads one step per time unit in each direction not blocked by a lion. A vertex is cleared from its contamination whenever a lion moves to it. Brass et al. [5] showed that n/2 lions are not enough to clear the n x n-grid. In this paper, we consider the same problem in dimension d 〉 2 and prove that Θ(nd-1/√d) lions are necessary and sufficient to clear the nd-grid. Furthermore, we analyze a problem variant where the lions are also allowed to jump from grid vertices to non-adjacent grid vertices.

Electronic ISSN: 1999-4893

Topics: Computer Science

Published by MDPI Publishing

	Location	Call Number	Expected	Availability

Others were also interested in ...

PAPER CURRENT

S·F·X

Fulltext

hit 1 - 1 | 1 hit