Em Busca de Redes Esparsas Robustas e Eficientes
Resumo
Motivados pela importância de construir redes eficientes e robustas, apresentamos um algoritmo eficiente para calcular a soma das distâncias em redes esparsas. Tal índice, também chamado de índice de Wiener, está relacionado com a eficiência da rede. Aplicando o algoritmo, discutimos algumas propriedades das redes robustas (biconexas) e eficientes (com pequena soma das distâncias).
Palavras-chave:
grafos, algoritmos em grafos, índice de Wiener, esparsidade, biconectividade
Referências
Bollobás, B. (2004). Extremal graph theory. Courier Corporation.
Brendan McKay, Adolfo Piperno (2022). Nauty traces. Acessado em 7 abril 2022.
Chepoi, V. and Klavzar, S. (1997). The Wiener index and the Szeged index of benzenoid systems in linear time. Journal of chemical info. computer science, 37(4):752–755.
Dankelmann, P., Gutman, I., Mukwembi, S., and Swart, H. C. (2009). The edge-wiener index of a graph. Discrete Mathematics, 309(10):3452–3457.
Deng, H., Xiao, H., and Tang, F. (2010). On the extremal wiener polarity index of trees with a given diameter. MATCH Commun. Math. Comput. Chem, 63(1):257–264.
Graovac, A. and Pisanski, T. (1991). On the wiener index of a graph. Journal of mathematical chemistry, 8(1):53–62.
Impagliazzo, R., Paturi, R., and Zane, F. (2001). Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512–530.
Klavzar, S., Gutman, I., and Mohar, B. (1995). Labeling of benzenoid systems which reflects the vertexdistance relations. Journal of chemical info. and comp. sci., 35(3):590–593.
Mohar, B. and Pisanski, T. (1988). How to compute the Wiener index of a graph. Journal of mathematical chemistry, 2(3):267–277.
Paul Manuel, Indra Rajasingh, Bharati Rajan, R. Sundara Rajan (2013). A new approach to compute wiener index. Journal Computational Theoretical Nanoscience https://arxiv.org/abs/1307.6502.
Roditty, L. and Vassilevska Williams, V. (2013). Fast approximation algorithms for the diameter and radius of sparse graphs. In STOC, pages 515–524.
Yeh, Y.-N. and Gutman, I. (1994). On the sum of all distances in composite graphs. Discrete Mathematics, 135(1-3):359–365.
Brendan McKay, Adolfo Piperno (2022). Nauty traces. Acessado em 7 abril 2022.
Chepoi, V. and Klavzar, S. (1997). The Wiener index and the Szeged index of benzenoid systems in linear time. Journal of chemical info. computer science, 37(4):752–755.
Dankelmann, P., Gutman, I., Mukwembi, S., and Swart, H. C. (2009). The edge-wiener index of a graph. Discrete Mathematics, 309(10):3452–3457.
Deng, H., Xiao, H., and Tang, F. (2010). On the extremal wiener polarity index of trees with a given diameter. MATCH Commun. Math. Comput. Chem, 63(1):257–264.
Graovac, A. and Pisanski, T. (1991). On the wiener index of a graph. Journal of mathematical chemistry, 8(1):53–62.
Impagliazzo, R., Paturi, R., and Zane, F. (2001). Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512–530.
Klavzar, S., Gutman, I., and Mohar, B. (1995). Labeling of benzenoid systems which reflects the vertexdistance relations. Journal of chemical info. and comp. sci., 35(3):590–593.
Mohar, B. and Pisanski, T. (1988). How to compute the Wiener index of a graph. Journal of mathematical chemistry, 2(3):267–277.
Paul Manuel, Indra Rajasingh, Bharati Rajan, R. Sundara Rajan (2013). A new approach to compute wiener index. Journal Computational Theoretical Nanoscience https://arxiv.org/abs/1307.6502.
Roditty, L. and Vassilevska Williams, V. (2013). Fast approximation algorithms for the diameter and radius of sparse graphs. In STOC, pages 515–524.
Yeh, Y.-N. and Gutman, I. (1994). On the sum of all distances in composite graphs. Discrete Mathematics, 135(1-3):359–365.
Publicado
31/07/2022
Como Citar
PIRES, Romeu Lustosa; SERRADO, Carlos Bravo; MENASCHÉ, Daniel Sadoc.
Em Busca de Redes Esparsas Robustas e Eficientes. In: WORKSHOP EM DESEMPENHO DE SISTEMAS COMPUTACIONAIS E DE COMUNICAÇÃO (WPERFORMANCE), 21. , 2022, Niterói.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2022
.
p. 114-119.
ISSN 2595-6167.
DOI: https://doi.org/10.5753/wperformance.2022.223313.
