The edit distance in graphs: Methods, results, and generalizations
The edit distance in graphs: Methods, results, and generalizations
复制标题
图表中的编辑距离：方法、结果和概括
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Ryan R. Martin
中科院分区：
文献类型：
--
作者：
Ryan R. Martin
编辑距离是图空间上非常简单且自然的度量。在编辑距离问题中，我们修复图的遗传属性并根据该属性计算图的渐近最大编辑距离。这个量很难直接计算，但在许多情况下，它可以作为编辑距离函数的最大值导出。 Szemeredi 的正则引理、强正则图、与 Zarankiewicz 问题相关的构造——所有这些都在编辑距离函数的计算中发挥着作用。最强大的工具来自对称化，我们用它来优化定义编辑距离函数的二次程序。在本文中，我们描述了一些用于计算编辑距离函数的最常用工具，总结了当前的主要结果，概述了对其他组合结构的概括，并提出了一些开放性问题。
The edit distance is a very simple and natural metric on the space of graphs. In the edit distance problem, we fix a hereditary property of graphs and compute the asymptotically largest edit distance of a graph from the property. This quantity is very difficult to compute directly but in many cases, it can be derived as the maximum of the edit distance function. Szemeredi’s regularity lemma, strongly regular graphs, constructions related to the Zarankiewicz problem – all these play a role in the computing of edit distance functions. The most powerful tool is derived from symmetrization, which we use to optimize quadratic programs that define the edit distance function. In this paper, we describe some of the most common tools used for computing the edit distance function, summarize the major current results, outline generalizations to other combinatorial structures, and pose some open problems.