Premium
All‐port line broadcasting in highly connected graphs
Author(s) -
Gaber Iris,
Parnas Michal
Publication year - 2005
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20055
Subject(s) - computer science , combinatorics , vertex (graph theory) , graph , hypercube graph , undirected graph , broadcasting (networking) , line graph , theoretical computer science , computer network , mathematics , graph power
In this article we propose polynomial time broadcasting protocols for an undirected graph under the circuit switched all‐port model. In this model one vertex initiates a message and must inform all vertices of the graph of the message. The message is passed between the vertices of the graph in a sequence of rounds, where during a round the vertices communicate along edge disjoint paths. Our algorithms will require the graph to have a certain edge connectivity lower bound, to achieve fast broadcasting time. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(2), 95–103 2005