Levenshtein graphs: Resolvability, automorphisms & determining sets
Levenshtein graphs: Resolvability, automorphisms & determining sets
复制标题
编辑图：可解析性、自同构
DOI：
10.1016/j.disc.2022.113310
复制
发表时间：
2023
影响因子：
0.8
通讯作者：
Lladser, Manuel E.
中科院分区：
文献类型：
--
作者：
Ruth, Perrin E.;Lladser, Manuel E.
我们引入Levenshtein图的概念，类似于Hamming图，但使用编辑距离而不是Hamming距离;特别是，Levenshtein图中的顶点可能是可能不同长度的字符串（即，参考字母表中的单词或字符序列）。我们研究了这些图的各种性质，包括它们的最短路距离与编辑距离相等的充分必要条件，并刻画了它们的自同构群和判定数.我们还限制了Levenshtein图的度量维数（即最小可分辨集大小）。关于后者，回想一下run是由相同字符组成的字符串。我们构造了一个两次运行字符串的解析集和一个算法，该算法计算长度为k的字符串与任何单次运行或两次运行字符串之间的编辑距离，时间复杂度为O（k）。
We introduce the notion of Levenshtein graphs, an analog to Hamming graphs but using the edit distance instead of the Hamming distance; in particular, vertices in Levenshtein graphs may be strings (ie, words or sequences of characters in a reference alphabet) of possibly different lengths. We study various properties of these graphs, including a necessary and sufficient condition for their shortest path distance to be identical to the edit distance, and characterize their automorphism group and determining number. We also bound the metric dimension (ie minimum resolving set size) of Levenshtein graphs. Regarding the latter, recall that a run is a string composed of identical characters. We construct a resolving set of two-run strings and an algorithm that computes the edit distance between a string of length k and any single-run or two-run string in O (k) operations.