Geodesic
Determining the Hausdorff Distance Between Trees in Polynomial Time
Discrete mathematics & theoretical computer science, Tome 23 (2021-2022) no. 3.

Voir la notice de l'article provenant de la source Episciences

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.
DOI : 10.46298/dmtcs.6952
Classification : 05C12, 05C85 
@article{DMTCS_2021_23_3_a1,
     author = {Kelenc, Aleksander},
     title = {Determining the {Hausdorff} {Distance} {Between} {Trees} in {Polynomial} {Time}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {23},
     number = {3},
     year = {2021-2022},
     doi = {10.46298/dmtcs.6952},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6952/}
}
TY  - JOUR
AU  - Kelenc, Aleksander
TI  - Determining the Hausdorff Distance Between Trees in Polynomial Time
JO  - Discrete mathematics & theoretical computer science
PY  - 2021-2022
VL  - 23
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6952/
DO  - 10.46298/dmtcs.6952
LA  - en
ID  - DMTCS_2021_23_3_a1
ER  - 
%0 Journal Article
%A Kelenc, Aleksander
%T Determining the Hausdorff Distance Between Trees in Polynomial Time
%J Discrete mathematics & theoretical computer science
%D 2021-2022
%V 23
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6952/
%R 10.46298/dmtcs.6952
%G en
%F DMTCS_2021_23_3_a1
Kelenc, Aleksander. Determining the Hausdorff Distance Between Trees in Polynomial Time. Discrete mathematics & theoretical computer science, Tome 23 (2021-2022) no. 3. doi : 10.46298/dmtcs.6952. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.6952/

Cité par Sources :