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

Abbas Cheraghi

doi:10.17485/ijst/2016/v9i13/71360

Article

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

VIEWS 728
PDF 214

Abstract
Full-Text HTML
Full-Text PDF
How to Cite

Indian Journal of Science and Technology

DOI: 10.17485/ijst/2016/v9i13/71360

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

Original Article

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

Abbas Cheraghi^*

*Author for correspondence
Abbas Cheraghi Department of Mathematics and Statistics, Khansar, University of Isfahan, Isfahan, Iran; [email protected]

This work is licensed under a Creative Commons Attribution 4.0 International License.

Abstract

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