Enhanced compact models for the connected subgraph problem and for the shortest path problem in digraphs with negative cycles
DOI10.1016/J.COR.2013.01.002zbMATH Open1348.05138OpenAlexW2100195928MaRDI QIDQ336550FDOQ336550
Authors: Mohamed Haouari, Mehdi Mrad, Nelson Maculan 
Publication date: 10 November 2016
Published in: Computers \& Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.cor.2013.01.002
Recommendations
- A strong flow-based formulation for the shortest path problem in digraphs with negative cycles
- Valid inequalities and lifting procedures for the shortest path problem in digraphs with negative cycles
- Integer programming formulations for the elementary shortest path problem
- New formulations for the elementary shortest-path problem visiting a given set of nodes
- Exact methods for solving the elementary shortest and longest path problems
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Paths and cycles (05C38)
Cites Work
- A note on two problems in connexion with graphs
- Title not available (Why is that?)
- Integer Programming Formulation of Traveling Salesman Problems
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Improved Algorithms for Detecting Negative Cost Cycles in Undirected Graphs
- The Steiner tree problem
- Column Generation
- A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems
- Solving VRPTWs with constraint programming based column generation
- Vehicle routing problem with elementary shortest path based column generation
- New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints
- A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints
- A strong flow-based formulation for the shortest path problem in digraphs with negative cycles
- On Tightening the Relaxations of Miller-Tucker-Zemlin Formulations for Asymmetric Traveling Salesman Problems
- Resource constrained shortest path problems in path planning for fleet management
- Tight compact models and comparative analysis for the prize collecting Steiner tree problem
- Space-time tradeoffs in negative cycle detection - an empirical analysis of the stressing algorithm
- The Floyd-Warshall algorithm on graphs with negative cycles
Cited In (8)
- Allocating nodes to hubs for minimizing the hubs processing resources: A case study
- A strong flow-based formulation for the shortest path problem in digraphs with negative cycles
- Theory and application of reciprocal transformation of “path problem” and “time float problem”
- Spatial optimization of multiple area land acquisition
- Small-\(m\) method for detecting all longest paths
- Integer programming formulations for the elementary shortest path problem
- MTZ-primal-dual model, cutting-plane, and combinatorial branch-and-bound for shortest paths avoiding negative cycles
- Tight lower bounds for the traveling salesman problem with draft limits
This page was built for publication: Enhanced compact models for the connected subgraph problem and for the shortest path problem in digraphs with negative cycles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q336550)
