DID YOU KNOW? DTIC has over 3.5 million final reports on DoD funded research, development, test, and evaluation activities available to our registered users. Click
HERE to register or log in.
Accession Number:
ADA066099
Title:
A Class of Solutions to the Gossip Problem.
Descriptive Note:
Technical rept.,
Corporate Author:
STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE
Report Date:
1979-01-01
Pagination or Media Count:
64.0
Abstract:
We characterize and count optimal solutions to the gossip problem in which no one hears his own information. That is, we consider graphs with n vertices where the edges have a linear ordering such that an increasing path exists from each vertex to every other, but there is no increasing path from any vertex to itself. Such graphs exist only when n is even, in which case the fewest number of edges is 2n-4, as in the original gossip problem. The characterize optimal solutions of this sort NOHO-graphs using a correspondence with a set of permutations and binary sequences. This correspondence enables us to count these solutions and several subclasses of solutions. The numbers of solutions in each class are simple powers of 2 and 3, with exponents determined by n. We also show constructively that NOHO-graphs are planar and Hamiltonian, and we mention applications to related problems. Author
Distribution Statement:
APPROVED FOR PUBLIC RELEASE