Séminaire Lotharingien de Combinatoire, B15h (1986).
[Formerly: Publ. I.R.M.A. Strasbourg, 1987, 340/S-15, p.
101-104.]
Eberhard Triesch
Kantensuche in Graphen
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 the problem of determining the
minimum number of questions is NP-complete.
The following version is available:
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.