title: Coverage-maximization in networks under resource constraints.
abstract: Efficient coverage algorithms are essential for information search or dispersal in all kinds of networks. We define an extended coverage problem which accounts for constrained resources of consumed bandwidth B and time T . Our solution to the network challenge is here studied for regular grids only. Using methods from statistical mechanics, we develop a coverage algorithm with proliferating message packets and temporally modulated proliferation rate. The algorithm performs as efficiently as a single random walker but O(B(d-2)/d) times faster, resulting in significant service speed-up on a regular grid of dimension d . The algorithm is numerically compared to a class of generalized proliferating random walk strategies and on regular grids shown to perform best in terms of the product metric of speed and efficiency.
authors.affiliation: Department of Computer Science and Engineering, Indian Institute of Technology, Kharagpur 721302, India.
authors.forename: Subrata
authors.initials: S
authors.lastname: Nandi
authors.forename: Lutz
authors.initials: L
authors.lastname: Brusch
authors.forename: Andreas
authors.initials: A
authors.lastname: Deutsch
authors.forename: Niloy
authors.initials: N
authors.lastname: Ganguly