A dynamic programming algorithm for solving the \(k\)-color shortest path problem

DOI10.1007/s11590-020-01659-zzbMath1475.90119OpenAlexW3106189041MaRDI QIDQ2047192

Serena Fugaro, Tommaso Pastore, Paola Festa, Daniele Ferone

Publication date: 19 August 2021

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-020-01659-z

zbMATH Keywords

dynamic programmingnetwork optimizationconstrained shortest pathedge-colored network

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Dynamic programming (90C39)

Related Items

The resource constrained clustered shortest path tree problem: Mathematical formulation and Branch&Price solution algorithm, A generalized shortest path tour problem with time windows

Uses Software

• CPLEX

Cites Work

• Unnamed Item
• Unnamed Item
• Exact approaches for the orderly colored longest path problem: performance comparison
• Shortest path tour problem with time windows
• Symmetry helps: bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints
• A survey of resource constrained shortest path problems: Exact solution approaches
• A simple and fast label correcting algorithm for shortest paths