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 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.