logo móvil
Contáctanos

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

Descargar PDF

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


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.

Otros recursos que podrían interesarte

Temas Virtualpro