Utilização da Árvore SPQR para um Cálculo Mais Eficiente das Medidas de Conectividade Baseadas em Cortes de Vértices - Hepp, Henrique; Cohen, Jaime; Duarte Jr., Elias Procópio (Anais do Workshop de Testes e Tolerância a Falhas (WTF); 2016: Anais do XVII Workshop de Testes e Tolerância a Falhas, 2016)
A medida de conectividade κ 2 (v) de um vértice v em um grafo G é o número máximo de caminhos vértices disjuntos que há entre esse vértice e qualquer outro vértice desse grafo. A proposta desse trabalho é melhorar a eficiência do cálculo de κ 2 (v) através de um pré-processamento do grafo. Nessa etapa, é construída uma árvore SPQR que identifica as componentes triconexas do grafo. Dessa forma, o κ 2 (v) pode ser calculado separadamente para cada componente. A proposta foi implementada e testada em grafos que modelam casos concretos. Apresentamos resultados para grafos para os quais observou- se que o tempo de cálculo de com o pré-processamento é significativamente menor que o tempo para calcular κ 2 (v) no grafo original.