The CACTUS project


  • a cactus is a graph in which every edge is contained in at most one cycle
  • cacti are perfectly suited to store the set of global minimum cuts of a weighted graph compactly
  • the inclusion- and intersection-structure of the set of minimum cuts is mirrored by the cactus of a graph


  • exploit for separation procedures in the branch-and-cut approach to the TSP, CVRP, and similar problems
  • observation that properties of TSP support graphs carrying LP solutions can speed up cactus construction significantly
  • cactus construction is an essential part in our TSPSIR project (here)


  • cactus construction algorithm based on a completely new algorithmic idea to construct the cactus of a TSP support graph
  • preliminary experiments show that the new algorithm will be 10 to 100 times faster in practice than benchmark algorithms
  • memory requirement for construction reduced from GBytes to MBytes for relevant graph sizes compared to other algorithms


  • on the left is a TSP support graph with minimum cut value 2
  • the corresponding cactus on the right side stores the set of all global minimum cuts and mirrors its structure
  • remove two edges of a cycle or remove one bold tree-edge to disconnect the cactus and to get minimum cuts of the graph


Back Top

Research Group Discrete Optimization

Last Update: 22.10.2002     webmaster: comopt