Transmitting in the \(n\)-dimensional cube
type: Item
instance of: scholarly article
title: Transmitting in the \(n\)-dimensional cube
zbMATH Open document ID: 0765.68011
DOI: 10.1016/0166-218X(92)90121-P
published in: Discrete Applied Mathematics
publication date: 1993-01-16T00:00:00Z
review text: It is proved that for any integer \(n\) and for any sequence \(a_ 1,\dots,a_ k\) of \(k=\lceil n/2\rceil\) binary vectors of dimension \(n\) there is a binary vector \(z\) of dimension \(n\) such that the Hamming distance between \(z\) and \(a_ i\) is greater than \(k-i\) for \(i=1,\dots,k\). This result shows that the strategy of the lazy sender on the broadcast problem in the \(n\)-dimension cube with a sender is optimal.
reviewed by: Tao Renji
Mathematics Subject Classification ID: 68M10
Mathematics Subject Classification ID: 68W15
Mathematics Subject Classification ID: 94A99
zbMATH DE Number: 94296
zbMATH Keywords: Hamming distance
zbMATH Keywords: broadcast problem
zbMATH Keywords: \(n\)-dimension cube
author: Noga Alon
MaRDI profile type: Publication
cites work: ``Integer-making'' theorems
cites work: Balancing matrices with line shifts
cites work: Q3899809
full work available at URL: 0166-218x(92)90121-p
OpenAlex ID: W2030639873
Recommended article: Optimal broadcasting for locally twisted cubes
Recommended article: One-to-one communication in twisted cubes under restricted connectivity
Recommended article: Q4383620
Recommended article: Optimum broadcasting and personalized communication in hypercubes
Recommended article: Wormhole broadcast in hypercubes
Recommended article: Complexity analysis of broadcasting in hypercubes with restricted communication capabilities
Recommended article: Broadcasting in all-output-port cube-connected cycles with distance-insensitive switching
Recommended article: On broadcasting multiple messages in a \(d\)-dimensional grid
Recommended article: Algorithm of multidimensional data transmission using extremal uniform hypergraphs
description: scientific article; zbMATH DE number 94296