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
Personal Author(s):
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
Descriptors:
Subject Categories:
- Numerical Mathematics
- Cybernetics