Thumbnail
Access Restriction
Open

Author Hromkovic, Juraj ♦ Klasing, Ralf ♦ Unger, Walter ♦ Wagener, Hubert
Source CiteSeerX
Content type Text
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Hubert Wagener Department ♦ Computer Science University ♦ Gossip Complexity ♦ Germany Keywords ♦ Walter Unger ♦ Edge-disjoint Path Mode ♦ Ralf Klasing ♦ Communication Power ♦ Extended Abstract ♦ Hamiltonian Path Meet ♦ Main Result ♦ Communication Step ♦ Upper Bound ♦ Parallel Computation ♦ Ne Min ♦ Complete Binary Tree ♦ Delta Dlog ♦ Optimal Algorithm ♦ Juraj Hromkovic ♦ Communication Algorithm ♦ Two-way Edge-disjoint Path Mode
Description ) Juraj Hromkovic y , Ralf Klasing, Walter Unger, Hubert Wagener z Department of Mathematics and Computer Science University of Paderborn 33095 Paderborn, Germany Keywords: communication algorithms, parallel computations. Abstract The communication power of the one-way and two-way edge-disjoint path modes for broadcast and gossip is investigated. The complexity of communication algorithms is measured by the number of communication steps (rounds). The main results achieved are the following: 1. For each connected graph G n of n nodes, the complexity of broadcast in G n , B min (G n ), satisfies dlog 2 ne B min (G n ) dlog 2 ne+ 1. The complete binary trees meet the upper bound, and all graphs containing a Hamiltonian path meet the lower bound. 2. For each connected graph G n of n nodes, the one-way (two-way) gossip complexity R(G n ) (R 2 (G n )) satisfies dlog 2 ne R 2 (G n ) 2 \Delta dlog 2 ne + 1, 1:44 : : : log 2 n R(G n ) 2 \Delta dlog 2 ne + 2. All these lo...
Information and Computation
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article