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 - https://doi.org/10.46298/dmtcs.6952
Determining the Hausdorff Distance Between Trees in Polynomial TimeArticle

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.

    https://doi.org/10.46298/dmtcs.6952
    Source: arXiv.org:1907.01299
    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
    Licence: Attribution 4.0 International (CC BY 4.0)

    Classifications

    Mathematics Subject Classification 20201
    Sources:
    • [1] zbMATH Open.

    Publications

    Has review
    • 1 zbMATH Open

    Share and export

    Consultation statistics

    This page has been seen 737 times.
    This article's PDF has been downloaded 437 times.