Miembros \ Profesores \ Gregorio Hernández Peñalver \ Grafos

Grafos

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: