Geodesic
Kantensuche in Graphen
Séminaire lotharingien de combinatoire, Tome 15 (1986)

Voir la notice de l'acte provenant de la source Séminaire Lotharingien de Combinatoire website

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. 

@article{SLC_1986_15_a7,
     author = {Eberhard Triesch},
     title = {Kantensuche in {Graphen}},
     journal = {S\'eminaire lotharingien de combinatoire},
     publisher = {mathdoc},
     volume = {15},
     year = {1986},
     url = {http://geodesic.mathdoc.fr/item/SLC_1986_15_a7/}
}
TY  - JOUR
AU  - Eberhard Triesch
TI  - Kantensuche in Graphen
JO  - Séminaire lotharingien de combinatoire
PY  - 1986
VL  - 15
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SLC_1986_15_a7/
ID  - SLC_1986_15_a7
ER  - 
%0 Journal Article
%A Eberhard Triesch
%T Kantensuche in Graphen
%J Séminaire lotharingien de combinatoire
%D 1986
%V 15
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SLC_1986_15_a7/
%F SLC_1986_15_a7
Eberhard Triesch. Kantensuche in Graphen. Séminaire lotharingien de combinatoire, Tome 15 (1986). http://geodesic.mathdoc.fr/item/SLC_1986_15_a7/