Problema APSP via Dimensão-VC e Médias de Rademacher - Lima, Alane M. de; Vignatti, André L.; Silva, Murilo V. G. da (Anais do Encontro de Teoria da Computação (ETC), 2021)
Considere o problema de computar o caminho mínimo entre cada par de vértices (APSP) de um grafo, desde que o caminho tenha alta centralidade, sendo que a métrica de centralidade em questão reflete a "importância'' do caminho no grafo. Propomos um algoritmo para este problema que usa uma estratégia de amostragem baseada em Dimensão-VC e médias de Rademacher. No caso de grafos esparsos de diâmetro logarítmico, que comumente modelam situações reais, o tamanho da amostra é exponencialmente menor do que aquelas obtidas por técnicas clássicas (e.g.: Hoeffding e limitante da união).