Aleksander Kelenc - Determining the Hausdorff Distance Between Trees in Polynomial Time

dmtcs:6952 - Discrete Mathematics & Theoretical Computer Science, August 19, 2021, vol. 23, no. 3 -
Determining the Hausdorff Distance Between Trees in Polynomial Time

Authors: Aleksander Kelenc

The Hausdorff distance is a relatively new measure of similarity of graphs. The notion of the Hausdorff distance considers a special kind of a common subgraph of the compared graphs and depends on the structural properties outside of the common subgraph. There was no known efficient algorithm for the problem of determining the Hausdorff distance between two trees, and in this paper we present a polynomial-time algorithm for it. The algorithm is recursive and it utilizes the divide and conquer technique. As a subtask it also uses the procedure that is based on the well known graph algorithm of finding the maximum bipartite matching.

Volume: vol. 23, no. 3
Section: Discrete Algorithms
Published on: August 19, 2021
Accepted on: July 24, 2021
Submitted on: December 2, 2020
Keywords: Mathematics - Combinatorics,Computer Science - Discrete Mathematics,05C85, 05C05, 05C12, 05C70


Consultation statistics

This page has been seen 325 times.
This article's PDF has been downloaded 199 times.