FUNDAMENTALNAYA I PRIKLADNAYA MATEMATIKA

(FUNDAMENTAL AND APPLIED MATHEMATICS)

1997, VOLUME 3, NUMBER 3, PAGES 759-773

On one mathematical model of the background search algorithms and the quick algorithm for the two-dimensional domination problem

E. E. Gasanov
T. W. Mkhitarova

Abstract

View as HTML     View as gif image    View as LaTeX source

Background search algorithms are investigated and a mathematical model of these algorithms is suggested in this paper. This model is based on the concept of the informational network with switches (INS), but INS complexity measure takes into account the user processing times of answer elements. The quick background algorithm solving the two-dimensional domination problem is suggested. This algorithm requires linear memory. We note that nonbackground algorithm with constant average search time requires quadratic memory.

All articles are published in Russian.

Location: http://mech.math.msu.su/~fpm/eng/97/973/97308h.htm
Last modified: January 20, 2000