Searching for an edge in a graph
Martin Aigner, E. Triesch · Journal of Graph Theory · 1988
Abstract Consider the problem of determining the endpoints of an unknown edge x in a given graph G by asking questions of the form “Is vertex v an endpoint of edge e in G?”. Sharp upper and lower bounds are derived, and it is shown that determining the minimum number of questions in NP‐complete.