Tight Bounds on Mimimum Broadcast Networks

DOI10.1137/0404021zbMath0725.94016OpenAlexW1578934802MaRDI QIDQ5202962

David Peleg, Michelangelo Grigni

Publication date: 1991

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

Full work available at URL: https://doi.org/10.1137/0404021

zbMATH Keywords

Fibonacci numberscommunication networkbroadcast graph

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Applications of graph theory to circuits and networks (94C15)

Related Items (35)

Binary linear programming models for robust broadcasting in communication networks ⋮ Hierarchical broadcast networks ⋮ Minimum \(k\)-broadcast graphs ⋮ Some minimum broadcast graphs ⋮ The complexity of finding a broadcast center ⋮ A new construction of broadcast graphs ⋮ Improved upper and lower bounds fork-broadcasting ⋮ Time-relaxed broadcasting in communication networks ⋮ Broadcasting in general networks I: Trees ⋮ Broadcast graphs using new dimensional broadcast schemes for Knödel graphs ⋮ Broadcast Graphs Using New Dimensional Broadcast Schemes for Knödel Graphs ⋮ Upper bounds on the broadcast function using minimum dominating sets ⋮ More broadcast graphs ⋮ Efficient construction of broadcast graphs ⋮ Diametral broadcast graphs ⋮ The minimum broadcast time problem for several processor networks ⋮ Sparse broadcast graphs ⋮ Efficient broadcast trees for weighted vertices ⋮ An algorithm for constructing minimalc-broadcast networks ⋮ Broadcasting and spanning trees in de Bruijn and Kautz networks ⋮ Broadcasting in DMA-bound bounded degree graphs ⋮ Minimum broadcast digraphs ⋮ Broadcasting from multiple originators ⋮ k-Broadcasting in trees ⋮ A 1-relaxed minimum broadcast graph on 15 vertices. ⋮ On time-relaxed broadcasting networks ⋮ A linear algorithm for finding the k‐broadcast center of a tree ⋮ A New Construction of Broadcast Graphs ⋮ An approximation algorithm and dynamic programming for reduction in heterogeneous environments ⋮ The even adjacency split problem for graphs ⋮ On the structure of minimum broadcast digraphs ⋮ Compound constructions of broadcast networks ⋮ Time-relaxed Multi-Broadcasting in Communication Networks (EXTENDED ABSTRACT) ⋮ Gossip Latin square and the meet-all gossipers problem ⋮ Graph theoretical issues in computer networks

This page was built for publication: Tight Bounds on Mimimum Broadcast Networks