Una nota sobre el problema de transbordo de costo mínimo más rápido

Por • 3 oct, 2022 • Sección: Economía

Martín Skutella

Klinz y Woeginger (1995) demuestran que el problema de flujo más rápido de costo mínimo es NP-difícil. Por otro lado, el problema de flujo de costo mínimo más rápido se puede resolver de manera eficiente a través de una reducción directa al problema de flujo más rápido sin costos. De manera más general, mostramos cómo el problema de transbordo de costo mínimo más rápido se puede reducir al problema de transbordo más rápido que se puede resolver de manera eficiente, agregando así otro mosaico al rico panorama de complejidad de los flujos a lo largo del tiempo.

arXiv:2209.05558v1 [cs.DM]

Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS)

Post to Twitter

Escribe un comentario