Note: The Smallest Nonevasive Graph Property
A property of n-vertex graphs is called evasive if every algorithm testing this property by asking questions of the form “is there an edge between vertices u and v” requires, in the worst case, to ask about all pairs of vertices. Most “natural” graph properties are either evasive or conjectured to b...
Main Author: | |
---|---|
Format: | Article |
Language: | English |
Published: |
University of Zielona Góra
2014-11-01
|
Series: | Discussiones Mathematicae Graph Theory |
Subjects: | |
Online Access: | https://doi.org/10.7151/dmgt.1766 |