Séminaire Lotharingien de Combinatoire, B15h (1986).
[Formerly: Publ. I.R.M.A. Strasbourg, 1987, 340/S-15, p.
Kantensuche in Graphen
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 the problem of determining the
minimum number of questions is NP-complete.
The paper has been finally published as a joint paper with Martin Aigner
under the title
"Searching for an edge in a graph" in
J. Graph Theory 12 (1988), 45-57.