Uma Breve Revisão dos Algoritmos Modernos de Caminho Mais Curto e Técnicas de Otimização de Grafos

Tabela de Links

Abstrato e 1. Introdução

1.1 Nossa Contribuição

1.2 Configuração

1.3 O algoritmo

1. Trabalhos Relacionados

2. Algoritmo

   3.1 A Fase de Decomposição Estrutural

   3.2 A Fase de Roteamento

   3.3 Variantes do WormHole

3. Análise Teórica

   4.1 Preliminares

   4.2 Sublinearidade do Anel Interno

   4.3 Erro de Aproximação

   4.4 Complexidade de Consulta

4. Resultados Experimentais

   5.1 WormHole𝐸, WormHole𝐻 e BiBFS

   5.2 Comparação com métodos baseados em índice

   5.3 WormHole como primitiva: WormHole𝑀

Referências

2 TRABALHOS RELACIONADOS

Existe um vasto corpo de pesquisa sobre caminhos mais curtos e distâncias, abrangendo muitas décadas e incluindo centenas de algoritmos e heurísticas projetados para uma variedade de configurações. Aqui, revisamos apenas vários trabalhos que estão mais intimamente relacionados com o nosso. Para uma visão mais abrangente, consulte as pesquisas [42, 55] e referências nelas contidas.

\ Abordagens baseadas em índice. Como mencionado anteriormente, um conjunto ubíquo de algoritmos é baseado em abordagens de marco/esboço [37, 61, 62], sendo o Pruned Landmark Labeling (PLL) [5] talvez o mais influente. Estes algoritmos seguem um procedimento de duas etapas: a primeira etapa gera uma ordenação dos vértices de acordo com a importância (baseada em diferentes heurísticas), e a segunda etapa gera rotulagem a partir de árvores de caminho mais curto podadas construídas de acordo com a ordenação. Então, a distância mais curta entre um par arbitrário de vértices 𝑠 e t pode ser respondida rapidamente com base em seus rótulos. No entanto, mesmo com a poda, o PLL requer um tempo de configuração significativo. Portanto, houve muitas tentativas de paralelizá-lo [29, 37, 39].

\ Abordagens baseadas em incorporação. Algumas abordagens recentes aproveitam incorporações de grafos para estimar caminhos mais curtos. Como na aprendizagem de representação, eles buscam encontrar representações eficientes de distâncias entre pares de nós [64, 65]. Uma linha moderna de trabalho também considera incorporações hiperbólicas dos grafos, que estão intimamente relacionadas com decomposições de árvores, para responder a consultas de caminho mais curto [11, 33]. Trabalhos recentes também analisaram a aceleração deste processo usando métodos de aprendizagem profunda baseados em GPU [35, 47, 48]. Query-by-Sketch [57] considera a tarefa, relacionada mas incomparável, de responder a consultas de grafo de caminho mais curto, onde o objetivo é calcular um subgrafo contendo exatamente todos os caminhos mais curtos entre um dado par de vértices. Eles propõem um esquema de rotulagem alternativo para melhorar a escalabilidade e os tempos de consulta.

\

\ Abordagens baseadas em núcleo-periferia. Vários outros trabalhos exploram a estrutura de núcleo-periferia das redes [6, 13, 38]. Brady e Cohen [13] usam esquemas de roteamento compactos para projetar um algoritmo com pequeno erro aditivo baseado na semelhança da periferia com uma floresta. Akiba, Sommer e Kawarabayashi [6] exploram a propriedade de baixa largura de árvore fora do núcleo, e em [38], os autores projetam um índice baseado em Core-Tree para melhorar os tempos de pré-processamento em grafos massivos. Observamos que em todos esses resultados, a sobrecarga de memória é super-linear.

\ Grafos de pior caso. No lado teórico, houve muitos resultados sobre caminhos mais curtos exatos e aproximados em grafos de pior caso, por exemplo, [19, 20, 22, 49, 51, 67], com melhorias tão recentes quanto o ano passado. A maioria destes foca no caso de aproximação 2, investigado pela primeira vez no trabalho seminal de Aingworth et al. [4]. Direcionamos os leitores para a pesquisa de Zwick [66] sobre algoritmos de caminho mais curto exatos e aproximados, e a pesquisa de Sen [53] sobre oráculos de distância para grafos gerais com ênfase na redução do custo de pré-processamento. Notavelmente, porque fazemos uma suposição estrutural além do pior caso que é comum em grandes redes, nomeadamente, uma estrutura de núcleo-periferia, tanto nossos resultados quanto algoritmo diferem substancialmente da literatura teórica de pior caso.

\

:::info Autores:

(1) Talya Eden, Universidade Bar-Ilan (talyaa01@gmail.com);

(2) Omri Ben-Eliezer, MIT (omrib@mit.edu);

(3) C. Seshadhri, UC Santa Cruz (sesh@ucsc.edu).

:::

:::info Este artigo está disponível no arxiv sob licença CC BY 4.0.

:::

\