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


PDFTo preview full article text in PDF format click here

Get Free ReaderYou could obtain free Acrobat Reader from Adobe


Copyright © Olympiads in Informatics, Vilnius University Institute of Mathematics and Informatics, 2011