Utilização da Árvore SPQR para um Cálculo Mais Eficiente das Medidas de Conectividade Baseadas em Cortes de Vértices
Resumo
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.
Referências
Cohen, J., Duarte, E. P. and Schroeder, J. (2011). Connectivity Criteria for Ranking Network Nodes, Communications in Computer and Information Science (CCIS), Vol. 116. pp. 35-45.
Cohen, J. (2013). Algoritmos Paralelos para Árvores de Cortes e Medidas de Centralidade em Grafos, Tese de Doutorado, Departamento de Informática - Universidade Federal do Paraná,
Pires, K., Cohen, J. and Duarte, E. P. (2011). Medidas de Conectividade Baseadas em Cortes de Vertices para Redes Complexas, 12 Workshop de Testes e Tolerância a Falhas (WTF’2011), Anais do SBRC’2011.
Pires, K. (2011). Medidas de Conectividade Baseadas em Cortes de Vértices para Redes Complexas, Dissertação de Mestrado, Departamento de Informática - Universidade Federal do Paraná.
Gutwenger, C. (2010). Application of SPQR-Trees in the Planarization Approach for Drawing Graphs, Tese de Doutorado, Technischen Universität Dortmund an der Fakultät für Informatik.
Batagelj, V. and Mrvar, A. (2006). Pajek datasets. Disponível em http://vlado.fmf.uni-lj.si/pub/networks/data/, Acessado em dezembro de 2015.
Nagamochi, H. and Ibaraki, T. (2008). Algorithmic Aspects of Graph Connectivity, Cambridge University Press.
Duarte, E. P., Santini, R. and Cohen, J. (2004). Delivering Packets During the Routing Convergence Latency Interval Through Highly Connected Detours, DSN, pp. 495–. IEEE Computer Society.
Hopcroft, J. E. and Tarjan, R. E. (1972). Finding the Triconected Components of a Graph, Technical Report 72-140, Cornell University.
Di Battista, G. and Tamassia, R. (1996). On-Line Maintenance of Triconnected Components with SPQR-Trees, Algorithmica, Vol. 15, pp. 302-318.
Bu, D., Zhao, Y., Cai, L., Xue, H., Zhu, X., Lu, H., Zhang, J., Sun, S., Ling, L., Zhang, N., Li, G., Chen, R. (2003). Topological Structure Analysis of the Protein-protein Interaction Network in Budding Yeast, Nucleic acids research, Vol. 31(9), pp. 2443–2450.
Storchi, G., Dell’Olmo, P. and Gentili, M. (1999) Directed Road Network of the City of Rome (1999). Disponível em [link], acessado em dezembre de 2015.
Kleinberg, J. M., Leskovec J. and Faloutsos, C. (2007). Graph Evolution: Densification and Shrinking Diameters, ACM Transactions on Knowledge Discovery from Data (ACM TKDD).
Watts, D. J. and Strogatz, S. H. (1998). Collective Dynamics of ’Small-World’ Networks, Nature, Vol. 393(6684), pp. 440–442.
Cohen, J. (2013). Algoritmos Paralelos para Árvores de Cortes e Medidas de Centralidade em Grafos, Tese de Doutorado, Departamento de Informática - Universidade Federal do Paraná,
Pires, K., Cohen, J. and Duarte, E. P. (2011). Medidas de Conectividade Baseadas em Cortes de Vertices para Redes Complexas, 12 Workshop de Testes e Tolerância a Falhas (WTF’2011), Anais do SBRC’2011.
Pires, K. (2011). Medidas de Conectividade Baseadas em Cortes de Vértices para Redes Complexas, Dissertação de Mestrado, Departamento de Informática - Universidade Federal do Paraná.
Gutwenger, C. (2010). Application of SPQR-Trees in the Planarization Approach for Drawing Graphs, Tese de Doutorado, Technischen Universität Dortmund an der Fakultät für Informatik.
Batagelj, V. and Mrvar, A. (2006). Pajek datasets. Disponível em http://vlado.fmf.uni-lj.si/pub/networks/data/, Acessado em dezembro de 2015.
Nagamochi, H. and Ibaraki, T. (2008). Algorithmic Aspects of Graph Connectivity, Cambridge University Press.
Duarte, E. P., Santini, R. and Cohen, J. (2004). Delivering Packets During the Routing Convergence Latency Interval Through Highly Connected Detours, DSN, pp. 495–. IEEE Computer Society.
Hopcroft, J. E. and Tarjan, R. E. (1972). Finding the Triconected Components of a Graph, Technical Report 72-140, Cornell University.
Di Battista, G. and Tamassia, R. (1996). On-Line Maintenance of Triconnected Components with SPQR-Trees, Algorithmica, Vol. 15, pp. 302-318.
Bu, D., Zhao, Y., Cai, L., Xue, H., Zhu, X., Lu, H., Zhang, J., Sun, S., Ling, L., Zhang, N., Li, G., Chen, R. (2003). Topological Structure Analysis of the Protein-protein Interaction Network in Budding Yeast, Nucleic acids research, Vol. 31(9), pp. 2443–2450.
Storchi, G., Dell’Olmo, P. and Gentili, M. (1999) Directed Road Network of the City of Rome (1999). Disponível em [link], acessado em dezembre de 2015.
Kleinberg, J. M., Leskovec J. and Faloutsos, C. (2007). Graph Evolution: Densification and Shrinking Diameters, ACM Transactions on Knowledge Discovery from Data (ACM TKDD).
Watts, D. J. and Strogatz, S. H. (1998). Collective Dynamics of ’Small-World’ Networks, Nature, Vol. 393(6684), pp. 440–442.
Publicado
30/05/2016
Como Citar
HEPP, Henrique; COHEN, Jaime; DUARTE JR., Elias Procópio.
Utilização da Árvore SPQR para um Cálculo Mais Eficiente das Medidas de Conectividade Baseadas em Cortes de Vértices. In: WORKSHOP DE TESTES E TOLERÂNCIA A FALHAS (WTF), 17. , 2016, Salvador/BA.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2016
.
p. 16-27.
ISSN 2595-2684.
DOI: https://doi.org/10.5753/wtf.2016.22873.
