PROROUTING
PROROUTING
(PROximity
Graphs and ROUTING)
es una herramienta diseñada
para el estudio de grafos geométricos, en particular de los
grafos de proximidad, las estrategias de ruteo en ellos y sus propiedades.
La herramienta se empezó a desarrollar en 2004 y desde
entonces se le han añadido numerosas mejoras y aumento de
funciones. En este momento está disponible la versión 2.
A continuación se describen algunas de las
características de la aplicación.
Grafos de proximidad y estructuras geométricas en PROROUTING
- Grafo del vecino más cercano. Grafo de los k-vecinos más próximos. Par más próximo.
- Cierre convexo.
- Árbol generador de peso mínimo. Árbol generador de peso mínimo k-local.
- Grafo del disco unidad.
- Grafo de Vecindad Relativa.
- Grafo de Gabriel.
- Triangulación incremental. Triangulación voraz.
- Triangulación de Delaunay. Diagrama de Voronoi.
- Beta-esqueletos
- Grafo de proximidad por semiplanos.
- Familia de grafos theta-lambda.
- Theta grafo. Theta grafo dirigido. Theta grafo ordenado. "Sink spanner".
- Grafo de Yao. Grafo de Yao dirigido. Grafo Yao-Yao. Grafo de Yao simétrico.
Estrategias de ruteo en PROROUTING
- Ruteo voraz.
- Ruteo por brújula. Ruteo aleatorizado por brújula.
- Ruteo híbrido voraz-brújula.
- Ruteo Voronoi.
- Ruteo por caras (variantes 1 y 2). Ruteo voraz-cara-voraz.
- Ruteo ad-hoc para grafos theta-lambda.
- Estudio de la calidad de todas las estrategias de ruteo
Construcción de caminos y spanners en PROROUTING
- Caminos de longitud mínima en un grafo (algoritmo de Dijkstra)
- Algoritmo PathGreedy
- Algoritmo Sparse Spanner
- Cálculo de la dilación de todos los grafos construidos.
Los autores de
la herramienta, desarrollada de forma acumulativa en la Facultad de
Informática de la Universidad Politécnica de Madrid, son:
David Ramos (versión preliminar, julio 2004)
José María Gil (versión 1.0, julio 2007)
Víctor Chavero (versión 2.0, mayo 2009)
