This article is cited in 3 papers

A lower bound for the complexity of information networks for a partial ordering relation

È. È. Gasanov


Abstract: We study the search problems where the search relation is a partial order relation. We reveal the common property of these problems called the existence of principal chains. Using this property, we obtain a lower bound for the complexity of the search problems with the natural partial order relation given on the Boolean cube, and prove that the lower bound is asymptotically attainable.
This work was supported by the Russian Foundation for Basic Research, grant 95–01–00597.

UDC: 517.977

Received: 27.01.1996

DOI: 10.4213/dm548

 English version: Discrete Mathematics and Applications, 1996, 6:6, 585–598

Bibliographic databases:

• 
•