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

Fast Neighborhood Rendezvous Encontro rápido na vizinhança

Ryota EGUCHI, Naoki KITAMURA, Taisuke IZUMI

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

No problema do encontro, duas entidades computacionais (chamadas agentes) localizados em vértices diferentes em um gráfico devem se encontrar no mesmo vértice. Neste artigo, consideramos o síncrono problema de encontro de bairro, onde os agentes estão inicialmente localizados em dois vértices adjacentes. Embora este problema possa ser resolvido trivialmente em O(Δ) rodadas (Δ é o grau máximo do gráfico), é altamente desafiador revelar se esse problema pode ser resolvido em o(Δ) rodadas, mesmo assumindo a rica capacidade computacional dos agentes. O único resultado conhecido é que a complexidade de tempo do O($O(sqrt{n})$) rodadas são possíveis se o gráfico estiver completo e os agentes forem probabilísticos, assimétricos e puderem usar quadros brancos colocados em vértices. Nossa principal contribuição é esclarecer a situação (no que diz respeito a modelos computacionais e classes de grafos) admitindo tal algoritmo de encontro em tempo sublinear. Mais precisamente, apresentamos dois algoritmos que alcançam encontro rápido, assumindo adicionalmente grau mínimo limitado, identificador de vértice exclusivo, acessibilidade a IDs de vizinhança e randomização. O primeiro algoritmo é executado dentro de $ ilde{O}(sqrt{nDelta/delta} + n/delta)$ rodadas para grafos de grau mínimo maiores que $sqrt{n}$, onde n é o número de vértices no gráfico e δ é o grau mínimo do gráfico. O segundo algoritmo assume que o maior ID de vértice é O(n) e alcança complexidade de tempo $ ilde{O}left( rac{n}{sqrt{delta}} ight)$-round sem usar quadros brancos. Esses algoritmos atingem oComplexidade de rodada (Δ) no caso de $delta = {omega}(sqrt{n} log n)$ e δ=ω(n2/3log4/3n) respectivamente. Também provamos que quatro suposições não convencionais de nosso algoritmo, grau mínimo limitado, acessibilidade aos IDs de vizinhança, distância inicial um e randomização são inerentemente necessárias para atingir um encontro rápido. Ou seja, pode-se obter o Ω(n)-arredondar o limite inferior se qualquer um deles for removido.

Publicação
IEICE TRANSACTIONS on Information Vol.E105-D No.3 pp.597-610
Data de publicação
2022/03/01
Publicitada
2021/12/17
ISSN online
1745-1361
DOI
10.1587/transinf.2021EDP7104
Tipo de Manuscrito
PAPER
Categoria
Fundamentos de Sistemas de Informação

autores

Ryota EGUCHI
  Nagoya Institute of Technology
Naoki KITAMURA
  Nagoya Institute of Technology
Taisuke IZUMI
  Osaka University

Palavra-chave