| O problema de ponderação de rodadas aparece na operação de redes de telecomunicações sem-fio, via rádio, e pode ser enunciado como uma aplicação de coloração de grafos da seguinte forma. Os dados de entrada são um grafo G = (V,E) representando uma rede formada por estações (vértices de G) e alcances de emissão (arestas de G) e um vértice s de G como emissor de uma informação destinada a cada um dos demais vértices. A operação dessa rede é restrita pela ocorrência de interferências entre vizinhos de G, descritas por um grafo de interferência H cujos vértices são associados a arestas de G, e uma aresta ij em H indica que o envio de uma mensagem pela aresta i de G não pode ocorrer simultaneamente com um envio por j sem que haja interferência entre esses dois envios. Nesse contexto, uma rodada é um conjunto de envios mutuamente não interferentes, o que pode ser visto como um conjunto independente de H. O objetivo é estabelecer uma sequência de rodadas (o que corresponde a uma coloração de H) de forma a entregar as informações inicialmente em s para cada um de seus destinos no menor tempo possível.
No caso geral, em que tanto G como H são arbitrários, o problema de ponderação de rodadas é NP-Difícil. No entanto, soluções ótimas polinomiais são conhecidas para alguns casos particulares. Por exemplo, podem-se citar vários casos em que G é uma árvore enraizada no vértice s. Dependendo do número de caminhos partindo de s, têm-se resultados conhecidos para diferentes grafos de interferência H: se o número de caminhos for 1, o já está resolvido para qualquer H; se esse número for 2, os casos já resolvidos correspondem às interferências para emissões oriundas de vértices de distância d em G, para d = 1, 2, 3, 4; e, finalmente, se o número de caminhos é arbitrário, somente o caso em que interferência entre vizinhos em G.
Neste trabalho, o caso de interferências apenas entre vizinhos é resolvido para quando o grafo G forma um hipercubo. |