Levenshtein graphs: resolvability, automorphisms \& determining sets

DOI10.1016/J.DISC.2022.113310MaRDI QIDQ2689484zbMATH OpenOpenAlexFDO

Authors Perrin E. Ruth, Manuel E. Lladser

Publication date 10 March 2023

Published in Discrete Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/2107.06951

zbMATH Keywords

edit distanceHamming graphLevenshtein graphmultilaterationnode2vecresolving set

Mathematics Subject Classification ID

Distance in graphs (05C12) Combinatorial codes (94B25)

Recommendations

• On the Levenshtein automaton and the size of the neighbourhood of a word
• Computing the edit distance of a regular language
• scientific article; zbMATH DE number 7360012
• Fast string correction with Levenshtein automata
• scientific article; zbMATH DE number 2052917

Cites work

• Algorithms for approximate string matching
• Approximate matching of run-length compressed strings
• Approximation complexity of metric dimension problem
• Automorphisms group of generalized Hamming Graphs
• Biological Sequence Analysis
• Destroying automorphisms by fixing nodes
• Edit distance of run-length encoded strings.
• Efficient reconstruction of sequences from their subsequences of supersequences
• scientific article; zbMATH DE number 3494441 (Why is no real title available?)
• scientific article; zbMATH DE number 3544092 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3240929 (Why is no real title available?)
• Identifying graph automorphisms using determining sets
• Landmarks in graphs
• Low-dimensional representation of genomic sequences
• On the metric dimension of Cartesian powers of a graph
• Resolvability of Hamming graphs
• The complexity of theorem-proving procedures
• The determining number of a Cartesian product
• The String-to-String Correction Problem

Cited in

(4)

• Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications
• Levenshtein Graphs: Resolvability, Automorphisms & Determining Sets
• On the size distribution of the fixed-length Levenshtein balls with radius one
• Metric dimension and resolvability of Jaccard spaces

Describes a project that uses

Uses Software

• node2vec

This page was built for publication: Levenshtein graphs: resolvability, automorphisms \& determining sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2689484)