On the Hausdorff Distance between Some Families of Chemical Graphs

Aleksander Kelenc
Faculty of Natural Sciences and Mathematics, University of Maribor

Andrej Taranenko
Faculty of Natural Sciences and Mathematics, University of Maribor

PDF

Minisymposium: CHEMICAL GRAPH THEORY

Content: In chemistry, the problem known as similarity searching involves finding a set of molecules that are similar to a given sample molecule. The problem is tackled using graph theory and related algorithmic approaches involving some kind of measure of similarity of two graphs. In this talk we present some results about a recently introduced Hausdorff distance between some families of graphs that often appear in chemical graph theory. Next to a few results for general graphs, we determine formulae for the distance between paths and cycles. For trees some bounds are proved. Also, an exact (exponential time) algorithm for determining the distance between two arbitrary trees is presented. We give examples emphasizing the difference between this new measure and some other known approaches, also reasons why some well-known algorithms for trees may not suffice to determine the Hausdorff distance of two trees are shown.

Back to all abstracts