Distances Between Immersed Graphs: Metric Properties
Distances Between Immersed Graphs: Metric Properties
复制标题
DOI：
10.1007/s44007-022-00037-8
复制
发表时间：
2023-01
期刊：
影响因子：
--
通讯作者：
M. Buchin;E. Chambers;Pan Fang;Brittany Terese Fasy;Ellen Gasparovic;E. Munch;C. Wenk
中科院分区：
文献类型：
--
作者：
M. Buchin;E. Chambers;Pan Fang;Brittany Terese Fasy;Ellen Gasparovic;E. Munch;C. Wenk
度量空间中的图出现在广泛的数据集中，并且有大量的工作集中在比较、匹配或分析不同环境空间中的图集合。在本调查中，我们概述了可以在度量空间中浸入（在某些情况下，嵌入）的有限图集上定义的各种距离度量。对于每一个距离度量，我们回顾它们的定义，并研究它们满足度量的哪些性质。此外，我们比较了基于这些性质的距离度量，并讨论了它们的计算复杂度。
Graphs in metric spaces appear in a wide range of data sets, and there is a large body of work focused on comparing, matching, or analyzing collections of graphs in different ambient spaces. In this survey, we provide an overview of a diverse collection of distance measures that can be defined on the set of finite graphs immersed (and in some cases, embedded) in a metric space. For each of the distance measures, we recall their definitions and investigate which of the properties of a metric they satisfy. Furthermore we compare the distance measures based on these properties and discuss their computational complexity.