Question

We are given a $n \times n$ grid, where each node can maintain a single "active" edge with one of its 4 neighbors at each time step. The active edge of each node changes periodically clockwise or anticlockwise, in the sense that if, for example, at time $t$ node $v$ has an active edge with its upper neighbor, and it rotates clockwise, at times $t+1$, $t+2$ and $t+3$ it will maintain an active edge with its right, lower and left neighbors, respectively.

at time $t=0$ node $(i,j)$ holds a message, and at each time step a node that has already received the message can transfer it through an active edge to one of its neighbors, if that neighbor also maintains this edge as active at this time step.

I am looking for sufficient conditions (initial active edges configurations and rotation direction of all the nodes) such that the message can be transmitted to all nodes in the grid. It's clear this is predetermined by the initial conditions, and depends upon the connectivity of a graph G' that represents them (where neighboring nodes that both maintain an edge as active at some time step are connected in G'). Given that G' it's possible to find total broadcasting time by graph traversal (BFS). The main question is how to know if two edges share an active edge at some time step (given that their behavior is cyclic).

Thanks!

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top