• P-ISSN 0974-6846 E-ISSN 0974-5645

Indian Journal of Science and Technology


Indian Journal of Science and Technology

Year: 2016, Volume: 9, Issue: 13, Pages: 1-5

Original Article

Searching for an Unknown Edge in the Graph and its Tight Complexity Bounds


Assume that H is a graph and c(R,H) is the number of tests needed by an algorithm R in the worst case to find unknown edge e* of H. The aim is to set c(H) = minR c(R,H). In this paper, presented a straightforward proof of the tight lower bound on c(H) for a special class of graphs. This explicit new bound based on the combinatorial object might be used for key distribution algorithm. Moreover, presented a lower bound on c(H) and show this bound for the complexity is tight. 

Keywords: Combinatorial Search, Graph Searching, Group Testing, Key Distribution, Unknown Edge


Subscribe now for latest articles and news.