Journal or Publication Title:

Математические вопросы кибернетики и вычислительной техники=Կիբեռնետիկայի և հաշվողական տեխնիկայի մաթեմատիկական հարցեր=Mathematical problems of computer science

Date of publication:

2013

Volume:

40

ISSN:

0131-4645

Additional Information:

click here to follow the link

Other title:

Gossip խնդիրների հետազետումը "Լոկալ փոխանակման" մեթոդի միջոցով; Исследование Gossip проблем при помощи метода "Локальных перестановок"

Coverage:

5-12

Abstract:

In this paper the method of local interchange is introduced to investigate gossip problems. This method is based on a repetitive use of permute higher and permute lower operations, which map one gossip graph with n vertices to another by moving only its edges without changing the labels of edges (the moments of corresponding calls). Using this method we obtain minimum time gossip graphs in which no one hears his own information (NOHO graphs) from gossip graphs based on KnÄodel graphs. The value of minimal time is T = dlog ne. This method also allowed us to ¯nd an alternative way of the proof that the number of minimal necessary calls in gossip schemes is 2n¡4, n ¸ 4.

Publisher:

Изд-во НАН РА

Date created:

2013-09-10

Format:

pdf

Identifier:

oai:arar.sci.am:258785

Location of original object:

ՀՀ ԳԱԱ Հիմնարար գիտական գրադարան