Flujos estables a lo largo del tiempo
Autores: Cseh, Ágnes; Matuschke, Jannik; Skutella, Martin
Idioma: Inglés
Editor: MDPI
Año: 2013
Acceso abierto
Artículo científico
2013
Flujos estables a lo largo del tiempo
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Estabilidad
Flujos de red
Variante de preflujo-empuje
Algoritmo de Gale-Shapley
Tiempo pseudo-polinómico
Propiedades periódicas
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 38
Citaciones: Sin citaciones
En este documento, la noción de estabilidad se extiende a flujos de red a lo largo del tiempo. Como un dispositivo útil en nuestras demostraciones, presentamos una elegante variante de preflujo-empuje del algoritmo de Gale-Shapley que opera directamente en la red dada y calcula flujos estables en tiempo seudo-polinómico, tanto en el flujo estático como en el caso de flujo a lo largo del tiempo. Mostramos propiedades periódicas de flujos estables a lo largo del tiempo en redes con un horizonte de tiempo infinito. Finalmente, discutimos la influencia del almacenamiento en vértices, con resultados diferentes dependiendo de la prioridad de los bordes de retención correspondientes.
Descripción
En este documento, la noción de estabilidad se extiende a flujos de red a lo largo del tiempo. Como un dispositivo útil en nuestras demostraciones, presentamos una elegante variante de preflujo-empuje del algoritmo de Gale-Shapley que opera directamente en la red dada y calcula flujos estables en tiempo seudo-polinómico, tanto en el flujo estático como en el caso de flujo a lo largo del tiempo. Mostramos propiedades periódicas de flujos estables a lo largo del tiempo en redes con un horizonte de tiempo infinito. Finalmente, discutimos la influencia del almacenamiento en vértices, con resultados diferentes dependiendo de la prioridad de los bordes de retención correspondientes.