¿Cuál es el nombre de este tipo de problema de gráfico dirigido?

16

Tome un gráfico dirigido donde los bordes estén decorados con un número natural. Queremos el conjunto de todas las rutas entre dos vértices y modo que cada borde sucesivo en la ruta esté decorado con un número natural que sea mayor que el número natural que decora el borde anterior.solPAGv1v2

Una aplicación para esto sería los horarios de autobuses o trenes. Si está tratando de determinar las diferentes rutas entre dos ciudades en función de los traslados entre estaciones. (No puede tomar un segundo tren programado para partir antes de que llegue el primero).

Informalmente he estado llamando a esto un "gráfico programado". Pero no sé cuál es el nombre de esto en la literatura.

Cualquier referencia a algoritmos relacionados con esto también es de interés.

ds.algorithms reference-request graph-algorithms terminology Robar
fuente
ligeramente relacionado: cstheory.stackexchange.com/questions/5849/…
Artem Kaznatcheev
1
Si considera el gráfico lineal de y orienta los bordes desde un nodo con un número más bajo a un nodo con un número más alto, obtendrá un DAG G ' . Por el contrario, cualquier orientación acíclica de cualquier gráfico lineal se puede obtener de esta manera. Por lo tanto, su problema parece ser esencialmente igual al siguiente problema: dada una orientación acíclica de un gráfico lineal, encuentre todas las rutas dirigidas que unen un par de nodos dado. Pero no estoy seguro de si la propiedad de ser un gráfico lineal realmente ayuda aquí ... solsol′
Jukka Suomela

Respuestas:

14

Hasta donde sé, el problema a veces se llama "caminos no decrecientes", y se estudió desde los años 50. Ver por ejemplo este artículo: GJ Minty. Una variante sobre el problema de la ruta más corta, Investigación de operaciones, 6 (6): 882–883, 1958.

st

virgi
fuente