Determining the Hausdorff Distance Between Trees in Polynomial Time
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 th...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2021-08-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/6952/pdf |
| _version_ | 1797269983543164928 |
|---|---|
| author | Aleksander Kelenc |
| author_facet | Aleksander Kelenc |
| author_sort | Aleksander Kelenc |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:57:02Z |
| format | Article |
| id | doaj.art-0cd7bd764fcc4013847174157255c418 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:57:02Z |
| publishDate | 2021-08-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-0cd7bd764fcc4013847174157255c4182024-03-07T15:45:30ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502021-08-01vol. 23, no. 3Discrete Algorithms10.46298/dmtcs.69526952Determining the Hausdorff Distance Between Trees in Polynomial TimeAleksander KelencThe 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://dmtcs.episciences.org/6952/pdfmathematics - combinatoricscomputer science - discrete mathematics05c85, 05c05, 05c12, 05c70 |
| spellingShingle | Aleksander Kelenc Determining the Hausdorff Distance Between Trees in Polynomial Time Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics computer science - discrete mathematics 05c85, 05c05, 05c12, 05c70 |
| title | Determining the Hausdorff Distance Between Trees in Polynomial Time |
| title_full | Determining the Hausdorff Distance Between Trees in Polynomial Time |
| title_fullStr | Determining the Hausdorff Distance Between Trees in Polynomial Time |
| title_full_unstemmed | Determining the Hausdorff Distance Between Trees in Polynomial Time |
| title_short | Determining the Hausdorff Distance Between Trees in Polynomial Time |
| title_sort | determining the hausdorff distance between trees in polynomial time |
| topic | mathematics - combinatorics computer science - discrete mathematics 05c85, 05c05, 05c12, 05c70 |
| url | https://dmtcs.episciences.org/6952/pdf |
| work_keys_str_mv | AT aleksanderkelenc determiningthehausdorffdistancebetweentreesinpolynomialtime |