KIAM Main page Web Library  •  Publication Searh  Русский 
Publication

Article collection "Mathematical Problems of Cybernetics" №15, Moscow, 2006
Authors: Debrev E.V.
On unconditional edge tests for regular families of graphs
Abstract:
We consider unconditional edge tests for undirected graphs without loops and multiple edges given on a fixed finite set of numbered vertices. For each regular family consisting of graphs with not more than two vertex similarity classes, we obtain upper and lower bounds of the minimal volume of such a test, differing not more than 8 times. Taking into account the previously obtained results, for all regular families of graphs on n numbered vertices, we find the order of n growth of the minimum volume of an unconditional edge test.
Keywords:
unconditional edge test, regular family of graphs
Publication language: russian,  pages: 16 (p. 183-198)
Research direction:
Mathematical problems and theory of numerical methods
Russian source text:
Export link to publication in format:   RIS    BibTex