A bridge between the minimal doubly resolving set problem in (folded) hypercubes and the coin weighing problem

DOI10.1016/j.dam.2021.11.016zbMath1480.05046arXiv2012.00396OpenAlexW4200590296MaRDI QIDQ2065777

Qingjie Ye, Chang-hong Lu

Publication date: 13 January 2022

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

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

zbMATH Keywords

hypercubeHamming graphmetric dimensioncoin weighing problemdoubly resolving set

Mathematics Subject Classification ID

Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

The doubly metric dimension of cylinder graphs and torus graphs

Cites Work

• Minimal doubly resolving sets and the strong metric dimension of some convex polytopes
• The (weighted) metric dimension of graphs: hard and easy cases
• Mastermind
• Computing the metric dimension of graphs by genetic algorithms
• Computing minimal doubly resolving sets of graphs
• Resolvability in graphs and the metric dimension of a graph
• Symmetry properties of resolving sets and metric bases in hypercubes
• Variable neighborhood search for metric dimension and minimal doubly resolving set problems
• An IP-based swapping algorithm for the metric dimension and minimal doubly resolving set problems in hypercubes
• On metric dimension of nonbinary Hamming spaces
• On the metric dimension of the folded \(n\)-cube
• Extremal graph theory for metric dimension and diameter
• On the metric dimension of Cartesian powers of a graph
• Landmarks in graphs
• Approximability of the Minimum Weighted Doubly Resolving Set Problem
• The metric dimension of small distance-regular and strongly regular graphs
• Base size, metric dimension and other invariants of groups and graphs
• On the Metric Dimension of Cartesian Products of Graphs
• Reducibility among Combinatorial Problems
• On a Combinatorial Problem in Number Theory
• Minimal doubly resolving sets and the strong metric dimension of Hamming graphs
• Determination of a Subset from Certain Combinatorial Properties
• On Metric Generators of Graphs
• Graph-Theoretic Concepts in Computer Science
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A bridge between the minimal doubly resolving set problem in (folded) hypercubes and the coin weighing problem