Aproximación del diámetro del gráfico distribuido
Autores: Ceccarello, Matteo; Pietracaprina, Andrea; Pucci, Geppino; Upfal, Eli
Idioma: Inglés
Editor: MDPI
Año: 2020
Acceso abierto
Artículo científico
2020
Aproximación del diámetro del gráfico distribuido
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Algoritmo
Diámetro
Grafos ponderados
Plataformas distribuidas
MapReduce
Aproximación
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 38
Citaciones: Sin citaciones
Presentamos un algoritmo para aproximar el diámetro de grafos ponderados masivos no dirigidos en plataformas distribuidas que admiten una abstracción similar a MapReduce. Para ser eficiente en términos de tiempo y espacio, nuestro algoritmo se basa en una estrategia de descomposición que divide el grafo en grupos disjuntos de radio acotado. Teóricamente, nuestro algoritmo utiliza espacio lineal y proporciona una garantía de aproximación polilogarítmica; lo más importante es que, para una gran familia de grafos, presenta una complejidad de rondas asintóticamente menor que la exhibida por un algoritmo de aproximación natural basado en el algoritmo SSSP de -stepping de última generación, que es su único competidor práctico en espacio lineal en el entorno distribuido. Complementamos nuestros hallazgos teóricos con un análisis experimental de prueba de concepto en grandes grafos de referencia, que sugiere que nuestro algoritmo puede lograr mejoras sustanciales en términos de tiempo de ejecución en comparación con el competidor mencionado anteriormente, al tiempo que presenta, en la práctica, una proporción de aproximación similar.
Descripción
Presentamos un algoritmo para aproximar el diámetro de grafos ponderados masivos no dirigidos en plataformas distribuidas que admiten una abstracción similar a MapReduce. Para ser eficiente en términos de tiempo y espacio, nuestro algoritmo se basa en una estrategia de descomposición que divide el grafo en grupos disjuntos de radio acotado. Teóricamente, nuestro algoritmo utiliza espacio lineal y proporciona una garantía de aproximación polilogarítmica; lo más importante es que, para una gran familia de grafos, presenta una complejidad de rondas asintóticamente menor que la exhibida por un algoritmo de aproximación natural basado en el algoritmo SSSP de -stepping de última generación, que es su único competidor práctico en espacio lineal en el entorno distribuido. Complementamos nuestros hallazgos teóricos con un análisis experimental de prueba de concepto en grandes grafos de referencia, que sugiere que nuestro algoritmo puede lograr mejoras sustanciales en términos de tiempo de ejecución en comparación con el competidor mencionado anteriormente, al tiempo que presenta, en la práctica, una proporción de aproximación similar.