A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

A Scheduling Problem in Multihop Networks Um problema de agendamento em redes Multihop

Kaoru WATANABE, Masakazu SENGOKU, Hiroshi TAMURA, Keisuke NAKANO, Shoji SHINODA

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

Em uma rede multihop, os pacotes de rádio são frequentemente retransmitidos através de estações intermediárias (repetidoras) para transferir um pacote de rádio de uma origem para seu destino. Consideramos um problema de escalonamento em uma rede multihop usando um modelo grafoteórico. Deixar D=(V,A) seja o dígrafo com um conjunto de vértices V e um conjunto de arco A. Deixei f ser uma rotulagem de inteiros positivos nos arcos de A. O valor de f(u,v) significa uma faixa de frequência atribuída no link de u para v. Nós chamamos f antitransitivo se f(u,v)f(v,w) para quaisquer arcos adjacentes (u,v) E (v,w) do D. O problema de rotulagem antitransitiva mínima é o problema de encontrar uma rotulagem antitransitiva mínima tal que o número de inteiros atribuídos em uma rotulagem antitransitiva seja mínimo. Neste artigo, provamos que este problema é NP-difícil e propomos um algoritmo simples de aproximação distribuída para ele.

Publicação
IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.6 pp.1222-1227
Data de publicação
2000/06/25
Publicitada
ISSN online
DOI
Tipo de Manuscrito
PAPER
Categoria
Gráficos e Redes

autores

Palavra-chave