Sobre emparejamientos estables y flujos
Autores: Fleiner, Tamás
Idioma: Inglés
Editor: MDPI
Año: 2014
Acceso abierto
Artículo científico
2014
Sobre emparejamientos estables y flujos
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Modelo de flujo
Emparejamientos estables
Emparejamientos máximos
Grafos bipartitos
Flujo estable
Matrimonios estables
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 39
Citaciones: Sin citaciones
Describimos un modelo de flujo relacionado con flujos de red ordinarios de la misma manera que los emparejamientos estables están relacionados con los emparejamientos máximos en grafos bipartitos. Demostramos que siempre existe un flujo estable y generalizamos la estructura de enrejado de los matrimonios estables a los flujos estables. Nuestra herramienta principal es una reducción directa del problema de flujo estable a asignaciones estables. Para ser completos, demostramos los resultados que necesitamos sobre asignaciones estables como una aplicación del teorema del punto fijo de Tarski.
Descripción
Describimos un modelo de flujo relacionado con flujos de red ordinarios de la misma manera que los emparejamientos estables están relacionados con los emparejamientos máximos en grafos bipartitos. Demostramos que siempre existe un flujo estable y generalizamos la estructura de enrejado de los matrimonios estables a los flujos estables. Nuestra herramienta principal es una reducción directa del problema de flujo estable a asignaciones estables. Para ser completos, demostramos los resultados que necesitamos sobre asignaciones estables como una aplicación del teorema del punto fijo de Tarski.