A lower bound for the recognition of digraph properties (Q810043)
From MaRDI portal
![]() | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A lower bound for the recognition of digraph properties |
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A lower bound for the recognition of digraph properties |
scientific article |
Statements
A lower bound for the recognition of digraph properties (English)
0 references
1990
0 references
A digraph may be viewed as a subset of the edges on the node set. A collection of such digraphs is called a digraph property provided that it is invariant under renumbering of the nodes. The complexity of a digraph property is the number of entries of the adjacency matrix which must be examined by a decision tree algorithm to recognize the property in the worst case. It is shown that every digraph property which is monotone, being not distroyed by the deletion of edges, and nontrivial, being held for some but not all digraphs, has a lower bound of \(v^ 2/2-O(v^ 2)\) for its complexity, where v is the number of nodes in the digraph. In addition, it is shown that a certain class of monotone, nontrivial bipartite digraph properties is evasive, requiring that every entry in the adjacency matrix be examined in the worst case.
0 references
digraph
0 references
complexity
0 references
adjacency matrix
0 references