Valid inequalities and lifting procedures for the shortest path problem in digraphs with negative cycles

DOI10.1007/s11590-014-0747-5zbMath1309.05085OpenAlexW2060673920MaRDI QIDQ2017836

M. S. Ibrahim, Michel Minoux, Nelson F. Maculan

Publication date: 23 March 2015

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

Full work available at URL: https://doi.org/10.1007/s11590-014-0747-5

zbMATH Keywords

shortest pathliftingpolytopedigraphsvalid inequality

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20)

Related Items

MTZ-primal-dual model, cutting-plane, and combinatorial branch-and-bound for shortest paths avoiding negative cycles, An efficient cutting plane algorithm for the minimum weighted elementary directed cycle problem in planar digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Finding small simple cycle separators for 2-connected planar graphs
• The directed subgraph homeomorphism problem
• Finding all the negative cycles in a directed graph
• A zero-space algorithm for negative cost cycle detection in networks
• A strong flow-based formulation for the shortest path problem in digraphs with negative cycles
• On a routing problem
• A Separator Theorem for Planar Graphs
• Generalized Nested Dissection
• On the shortest path problem with negative cost cycles