Levenshtein graphs: resolvability, automorphisms \& determining sets

DOI10.1016/J.DISC.2022.113310OpenAlexW4316015021MaRDI QIDQ2689484FDOQ2689484

Authors: Perrin E. Ruth, Manuel E. Lladser 

Publication date: 10 March 2023

Published in: Discrete Mathematics (Search for Journal in Brave)

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

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

zbMATH Keywords

node2vecedit distanceresolving setHamming graphmultilaterationLevenshtein graph

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (2)

• Levenshtein Graphs: Resolvability, Automorphisms & Determining Sets
• Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications

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)