Labeled versus unlabeled distributed Cayley networks
We consider labelings (i.e. assignments of labels to the links that give the network a globally consistent orientation) on anonymous Cayley networks NG constructed from a set G of generators of a group G. Such networks can be endowed with a natural labeling LG to form the oriented Cayley network, denoted by NG[LG]. We show that in general oriented Cayley networks are more powerful than unoriented Cayley networks, in the sense that the former can compute more Boolean functions than the latter. We also give a characterization of those Abelian groups G which have a canonical set of generators G such that the network NG computes more Boolean functions than the network NG[LG].
|Keywords||Anonymous networks, Boolean function, Cayley networks, Group of automorphisms, Labeled and unlabeled networks|
|Journal||Discrete Applied Mathematics|
Kranakis, E, & Krizanc, D. (Danny). (1995). Labeled versus unlabeled distributed Cayley networks. Discrete Applied Mathematics, 63(3), 223–236. doi:10.1016/0166-218X(94)00070-3