An efficient cutting plane algorithm for the minimum weighted elementary directed cycle problem in planar digraphs

DOI10.1051/ro/2015052zbMath1349.90815OpenAlexW2506178252MaRDI QIDQ2826672

M. S. Ibrahim, Nelson F. Maculan, Hacene Ouzia

Publication date: 18 October 2016

Published in: RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1051/ro/2015052

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Directed graphs (digraphs), tournaments (05C20)

Related Items (2)

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
• DRL\(^*\): A hierarchy of strong block-decomposable linear relaxations for 0-1 mips
• A fast algorithm for minimum weight odd circuits and cuts in planar graphs
• Matrix multiplication via arithmetic progressions
• On cardinality constrained cycle and path polytopes
• Efficient approximation algorithms for shortest cycles in undirected graphs
• The directed subgraph homeomorphism problem
• Valid inequalities and lifting procedures for the shortest path problem in digraphs with negative cycles
• An efficient cutting plane algorithm for the minimum weighted elementary directed cycle problem in planar digraphs
• On the cycle polytope of a directed graph and its relaxations
• A strong flow-based formulation for the shortest path problem in digraphs with negative cycles
• Finding a Minimum Circuit in a Graph
• Finding Even Cycles Even Faster
• Minimum Weight Cycles and Triangles: Equivalences and Algorithms
• On cycle cones and polyhedra

This page was built for publication: An efficient cutting plane algorithm for the minimum weighted elementary directed cycle problem in planar digraphs