Levenshtein graphs: Resolvability, automorphisms & determining sets
Copyright policy )Levenshtein graphs: Resolvability, automorphisms & determining sets
We introduce the notion of Levenshtein graphs, an analog to Hamming graphs but using the edit distance instead of the Hamming distance; in particular, Levenshtein graphs allow for underlying strings (nodes) of different lengths. We characterize various properties of these graphs, including a necessary and sufficient condition for their geodesic distance to be identical to the edit distance, their automorphism group and determining number, and an upper bound on their metric dimension. Regarding the latter, we construct a resolving set composed 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.
22 pages, 3 figures
- University of Colorado Boulder United States
- University of Colorado System United States
FOS: Computer and information sciences, Combinatorial codes, Distance in graphs, Discrete Mathematics (cs.DM), 05C12, 05C85, 68R10, 68W32, resolving set, edit distance, Levenshtein graph, multilateration, Hamming graph, Computer Science - Data Structures and Algorithms, FOS: Mathematics, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), Combinatorics (math.CO), node2vec, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Combinatorial codes, Distance in graphs, Discrete Mathematics (cs.DM), 05C12, 05C85, 68R10, 68W32, resolving set, edit distance, Levenshtein graph, multilateration, Hamming graph, Computer Science - Data Structures and Algorithms, FOS: Mathematics, Mathematics - Combinatorics, Data Structures and Algorithms (cs.DS), Combinatorics (math.CO), node2vec, Computer Science - Discrete Mathematics
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).1 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!