1
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ Welcome to CS.SE! Is the rotation direction the same at every time step, for a given node? Or can it change direction? If it can't change, you can check whether two nodes are "connected" (can send a message from one to the other) at time $t$ based solely on the initial configuration, rotation direction of all nodes, and the value of $t \bmod 4$. $\endgroup$ – D.W. Apr 25 '17 at 17:35
2
$\begingroup$

Here is how to analyze a starting configuration to determine whether the message will be able to eventually reach all nodes in the grid.

Consider two adjacent nodes $u,v$. We'll say that these two nodes are connected if at some point during the first four time steps, node $u$'s active edge points to $v$ and node $v$'s active edge points to $u$. In other words, nodes $u,v$ are connected if one (or both) of the following two conditions holds:

  1. In the initial configuration, $u$'s active edge points to $v$ and $v$'s active edge points to $u$.

  2. $u$ rotates in the opposite direction as $v$.

Construct an undirected graph $G$ with one vertex per node in the cell, and an edge $(u,v)$ between two vertices iff they are connected (per the above definition). Then a necessary and sufficient condition for the message to be able to reach all nodes in the grid is that the graph $G$ must be connected.


It's also possible to use this kind of analysis to determine the shortest time necessary before the message reaches all nodes, with running time linear in the size of the graph.

In particular, we can build a directed graph $G'$ with one vertex $(i,j,k)$ per cell $(i,j)$ and value $k \in \{0,1,2,3\}$. (We will interpret $k$ as the time, modulo 4.) This graph has a directed edge $(i,j,k) \to (i',j',k+1 \bmod 4)$ if $(i,j)$ is adjacent to $(i',j')$ and $(i,j)$'s active edge points to $(i',j')$ at time $k$ and $(i',j')$'s active edge points to $(i,j)$ at time $k$.

Now we use breadth-first search to find the shortest path from $(i_0,j_0,0)$ to every other vertex, where $(i_0,j_0)$ is the cell where the message starts. We define

$$f(i,j) = \min\{d((i_0,j_0,0),(i,j,k)) : k=0,1,2,3\}$$

where $d(u,v)$ is the length of the shortest path from vertex $u$ to vertex $v$ in $G'$. Finally, $\max_{i,j} f(i,j)$ is the shortest time necessary for the message to reach all nodes. The running time of this algorithm is $O(mn)$, i.e., it runs in linear time (linear in the size of the input).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.