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
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.
Ryota EGUCHI
Nagoya Institute of Technology
Naoki KITAMURA
Nagoya Institute of Technology
Taisuke IZUMI
Osaka University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copiar
Ryota EGUCHI, Naoki KITAMURA, Taisuke IZUMI, "Fast Neighborhood Rendezvous" in IEICE TRANSACTIONS on Information,
vol. E105-D, no. 3, pp. 597-610, March 2022, doi: 10.1587/transinf.2021EDP7104.
Abstract: In the rendezvous problem, two computing entities (called agents) located at different vertices in a graph have to meet at the same vertex. In this paper, we consider the synchronous neighborhood rendezvous problem, where the agents are initially located at two adjacent vertices. While this problem can be trivially solved in O(Δ) rounds (Δ is the maximum degree of the graph), it is highly challenging to reveal whether that problem can be solved in o(Δ) rounds, even assuming the rich computational capability of agents. The only known result is that the time complexity of O($O(sqrt{n})$) rounds is achievable if the graph is complete and agents are probabilistic, asymmetric, and can use whiteboards placed at vertices. Our main contribution is to clarify the situation (with respect to computational models and graph classes) admitting such a sublinear-time rendezvous algorithm. More precisely, we present two algorithms achieving fast rendezvous additionally assuming bounded minimum degree, unique vertex identifier, accessibility to neighborhood IDs, and randomization. The first algorithm runs within $ ilde{O}(sqrt{nDelta/delta} + n/delta)$ rounds for graphs of the minimum degree larger than $sqrt{n}$, where n is the number of vertices in the graph, and δ is the minimum degree of the graph. The second algorithm assumes that the largest vertex ID is O(n), and achieves $ ilde{O}left( rac{n}{sqrt{delta}}
ight)$-round time complexity without using whiteboards. These algorithms attain o(Δ)-round complexity in the case of $delta = {omega}(sqrt{n} log n)$ and δ=ω(n2/3log4/3n) respectively. We also prove that four unconventional assumptions of our algorithm, bounded minimum degree, accessibility to neighborhood IDs, initial distance one, and randomization are all inherently necessary for attaining fast rendezvous. That is, one can obtain the Ω(n)-round lower bound if either one of them is removed.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2021EDP7104/_p
Copiar
@ARTICLE{e105-d_3_597,
author={Ryota EGUCHI, Naoki KITAMURA, Taisuke IZUMI, },
journal={IEICE TRANSACTIONS on Information},
title={Fast Neighborhood Rendezvous},
year={2022},
volume={E105-D},
number={3},
pages={597-610},
abstract={In the rendezvous problem, two computing entities (called agents) located at different vertices in a graph have to meet at the same vertex. In this paper, we consider the synchronous neighborhood rendezvous problem, where the agents are initially located at two adjacent vertices. While this problem can be trivially solved in O(Δ) rounds (Δ is the maximum degree of the graph), it is highly challenging to reveal whether that problem can be solved in o(Δ) rounds, even assuming the rich computational capability of agents. The only known result is that the time complexity of O($O(sqrt{n})$) rounds is achievable if the graph is complete and agents are probabilistic, asymmetric, and can use whiteboards placed at vertices. Our main contribution is to clarify the situation (with respect to computational models and graph classes) admitting such a sublinear-time rendezvous algorithm. More precisely, we present two algorithms achieving fast rendezvous additionally assuming bounded minimum degree, unique vertex identifier, accessibility to neighborhood IDs, and randomization. The first algorithm runs within $ ilde{O}(sqrt{nDelta/delta} + n/delta)$ rounds for graphs of the minimum degree larger than $sqrt{n}$, where n is the number of vertices in the graph, and δ is the minimum degree of the graph. The second algorithm assumes that the largest vertex ID is O(n), and achieves $ ilde{O}left( rac{n}{sqrt{delta}}
ight)$-round time complexity without using whiteboards. These algorithms attain o(Δ)-round complexity in the case of $delta = {omega}(sqrt{n} log n)$ and δ=ω(n2/3log4/3n) respectively. We also prove that four unconventional assumptions of our algorithm, bounded minimum degree, accessibility to neighborhood IDs, initial distance one, and randomization are all inherently necessary for attaining fast rendezvous. That is, one can obtain the Ω(n)-round lower bound if either one of them is removed.},
keywords={},
doi={10.1587/transinf.2021EDP7104},
ISSN={1745-1361},
month={March},}
Copiar
TY - JOUR
TI - Fast Neighborhood Rendezvous
T2 - IEICE TRANSACTIONS on Information
SP - 597
EP - 610
AU - Ryota EGUCHI
AU - Naoki KITAMURA
AU - Taisuke IZUMI
PY - 2022
DO - 10.1587/transinf.2021EDP7104
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E105-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2022
AB - In the rendezvous problem, two computing entities (called agents) located at different vertices in a graph have to meet at the same vertex. In this paper, we consider the synchronous neighborhood rendezvous problem, where the agents are initially located at two adjacent vertices. While this problem can be trivially solved in O(Δ) rounds (Δ is the maximum degree of the graph), it is highly challenging to reveal whether that problem can be solved in o(Δ) rounds, even assuming the rich computational capability of agents. The only known result is that the time complexity of O($O(sqrt{n})$) rounds is achievable if the graph is complete and agents are probabilistic, asymmetric, and can use whiteboards placed at vertices. Our main contribution is to clarify the situation (with respect to computational models and graph classes) admitting such a sublinear-time rendezvous algorithm. More precisely, we present two algorithms achieving fast rendezvous additionally assuming bounded minimum degree, unique vertex identifier, accessibility to neighborhood IDs, and randomization. The first algorithm runs within $ ilde{O}(sqrt{nDelta/delta} + n/delta)$ rounds for graphs of the minimum degree larger than $sqrt{n}$, where n is the number of vertices in the graph, and δ is the minimum degree of the graph. The second algorithm assumes that the largest vertex ID is O(n), and achieves $ ilde{O}left( rac{n}{sqrt{delta}}
ight)$-round time complexity without using whiteboards. These algorithms attain o(Δ)-round complexity in the case of $delta = {omega}(sqrt{n} log n)$ and δ=ω(n2/3log4/3n) respectively. We also prove that four unconventional assumptions of our algorithm, bounded minimum degree, accessibility to neighborhood IDs, initial distance one, and randomization are all inherently necessary for attaining fast rendezvous. That is, one can obtain the Ω(n)-round lower bound if either one of them is removed.
ER -