Resolvability of Hamming graphs
From MaRDI portal
Publication:5128504
graph embeddingGröbner basisHamming distanceHamming graphhypercubeinteger linear programmingmetric dimensionmultilaterationresolving setsymbolic data science
Distance in graphs (05C12) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph representations (geometric and intersection representations, etc.) (05C62) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Graph theory (including graph drawing) in computer science (68R10) Programming involving graphs or networks (90C35) Biochemistry, molecular biology (92C40)
Abstract: A subset of vertices in a graph is called resolving when the geodesic distances to those vertices uniquely distinguish every vertex in the graph. Here, we characterize the resolvability of Hamming graphs in terms of a constrained linear system and deduce a novel but straightforward characterization of resolvability for hypercubes. We propose an integer linear programming method to assess resolvability rapidly, and provide a more costly but definite method based on Gr"obner bases to determine whether or not a set of vertices resolves an arbitrary Hamming graph. As proof of concept, we identify a resolving set of size 77 in the metric space of all octapeptides (i.e., proteins composed of eight amino acids) with respect to the Hamming distance; in particular, any octamer may be readily represented as a 77-dimensional real-vector. Representing k-mers as low-dimensional numerical vectors may enable new applications of machine learning algorithms to symbolic sequences.
Recommendations
Cites work
- A fast algorithm for particle simulations
- A modeling and computational study of the frustration index in signed networks
- A new efficient algorithm for computing Gröbner bases (F₄)
- Applied Linear Algebra
- Approximation complexity of metric dimension problem
- Best subset selection via a modern optimization lens
- F5C: A variant of Faugère's F5 algorithm with reduced Gröbner bases
- scientific article; zbMATH DE number 3644821 (Why is no real title available?)
- 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 1206418 (Why is no real title available?)
- scientific article; zbMATH DE number 1234104 (Why is no real title available?)
- scientific article; zbMATH DE number 2151220 (Why is no real title available?)
- scientific article; zbMATH DE number 1416629 (Why is no real title available?)
- Ideals, Varieties, and Algorithms
- Landmarks in graphs
- Low-dimensional representation of genomic sequences
- Multidimensional binary search trees used for associative searching
- Resolvability in graphs and the metric dimension of a graph
- Resolving the hypercube
- The complexity of theorem-proving procedures
- The F5 algorithm in Buchberger's style
- The metric dimension and metric independence of a graph
- Variable neighborhood search for metric dimension and minimal doubly resolving set problems
Cited in
(12)- The retracts of Hamming graphs
- Retracts of infinite Hamming graphs
- On existence of perfect bitrades in Hamming graphs
- On vertices contained in all or in no metric basis
- Levenshtein graphs: resolvability, automorphisms \& determining sets
- Recognizing Hamming graphs in linear time and space
- Resolving the Existence of Full-Rank Tilings of Binary Hamming Spaces
- On metric dimensions of hypercubes
- Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications
- Multi random projection inner product encryption, applications to proximity searchable encryption for the iris biometric
- The edge fault-tolerance about the strong Menger edge-connectivity of order r among Hamming graph
- Metric dimension and resolvability of Jaccard spaces
This page was built for publication: Resolvability of Hamming graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5128504)
