Bounded depth broadcasting
type: Item
instance of: scholarly article
title: Bounded depth broadcasting
zbMATH Open document ID: 0849.05041
DOI: 10.1016/0166-218X(94)00165-A
author: David B. Peters
author: Joseph G. Peters
published in: Discrete Applied Mathematics
publication date: 1996-11-05T00:00:00Z
review text: A broadcasting process with a bound on the number of retransmissions occurs, for example, where information degrades under repetition, or where photocopies do not retain the crispness of the original. The authors model such a process with graphs in which the depth of broadcast tree---spanning rooted trees originating at every vertex---cannot exceed \(d\); in any time unit each vertex that has been informed is permitted to communicate to at most one new vertex. The broadcast time of a graph \(G\) is the maximum of the broadcast times of all vertices \(u\); which, in turn, is the number of time units required, beginning at \(u\), to inform all vertices. The minimum broadcast time over all graphs \(G\) on \(n\) vertices is \(\pi_d(n)\); a graph \(G\) with broadcast time \(\tau_d(n)\) is called a broadcast graph. The minimum number of edges in a broadcast graph on \(n\) vertices is denoted by \(B_d(n)\); a graph attaining this minimum is a minimum broadcast graph. Conjecture 3.1: For any \(n\) and \(d\) there is a minimum broadcast graph with maximum degree \(\tau_d(n)\). ``Our main goal (\dots) is to develop methods for constructing good bounded depth broadcast graphs; we do this in Section 4. In Section 2 we exhibit a number of small optimal graphs, most of which are not produced by general constructions. In Section 3 we prove lower bounds on \(B_d(n)\).'' ``We present several general constructions that produce infinite families of optimal networks (minimum time and minimum number of [edges]). We also exhibit a number of small optimal networks that are not produced by the general construction''.
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 90B18
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 94C15
zbMATH DE Number: 897397
zbMATH Keywords: communication
zbMATH Keywords: broadcasting process
zbMATH Keywords: broadcast tree
zbMATH Keywords: broadcast time
zbMATH Keywords: broadcast graph
zbMATH Keywords: minimum broadcast graph
zbMATH Keywords: optimal networks
reviewed by: William G. Brown
MaRDI profile type: Publication
cites work: Antepenultimate broadcasting
cites work: Sparse broadcast graphs
cites work: Broadcasting in Bounded Degree Graphs
cites work: Q4038748
cites work: Minimal broadcast networks
cites work: Minimum broadcast graphs
cites work: Methods and problems of communication in usual networks
cites work: A survey of gossiping and broadcasting in communication networks
cites work: Broadcasting in DMA-bound bounded degree graphs
cites work: Minimum broadcast digraphs
cites work: Information Dissemination in Trees
full work available at URL: 0166-218x(94)00165-a
OpenAlex ID: W2056066741
Recommended article: Broadcasting in Bounded Degree Graphs
Recommended article: Broadcast Networks of Bounded Degree
Recommended article: Bounded-call broadcasting
Recommended article: Communication in bounded depth circuits
Recommended article: Broadcasting in DMA-bound bounded degree graphs
Recommended article: Q4223773
Recommended article: Broadcasting with linearly bounded transmission faults
Recommended article: Bounded-hop communication networks
Recommended article: Broadcasting in butterfly and deBruijn networks
Recommended article: General bounds on limited broadcast domination
description: scientific article; zbMATH DE number 897397