Geodesic
Kantensuche in Graphen
Séminaire lotharingien de combinatoire, Tome 15 (1986) Cet article a éte moissonné depuis la source Séminaire Lotharingien de Combinatoire website

Voir la notice de l'acte

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},
     year = {1986},
     volume = {15},
     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
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
%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/