OLYMPIADS IN INFORMATICS, 2011, Vol. 5, 82-91
© Institute of Mathematics and Informatics,
ISSN 1822-7732
Reconstruction of Trees Using Metric Properties
Krassimir MANEV, Nikolai NIKOLOV, Minko MARKOV
^1Department of Mathematics and Informatics, Sofia University ^{\ }\,J. Bourchier blvd. 5, 1164 Sofia, Bulgaria ^2Institute of Mathematics and Informatics, Bulgarian Academy of Sciences ^{\ }\,G. Bontchev str. 8, 1113 Sofia, Bulgaria E-mail: manev@fmi.uni-sofia.bg, nik@math.bas.bg, minkom@fmi.uni-sofia.bg
Abstract
To reconstruct a graph from some of its elements or characteristics is a hard problem. Reconstructions require very good mathematical background and programming skills. That is why some not so difficult graph reconstruction problems may be appropriate for competitions in programming both for university and school students. In this paper two such problems are considered - reconstruction of a tree from the distances between its outer vertices and from the distances between all its vertices. It is proved that any tree can be reconstructed in either case. The corresponding algorithms are presented and their time complexities are estimated.
Keywords:
graphs, trees, shortest paths, reconstruction of tree
To preview full
article text in PDF format click here
You
could obtain free Acrobat Reader from Adobe
Copyright © Olympiads in Informatics, Vilnius University Institute of Mathematics and Informatics, 2011
