COIN-OR::LEMON - Graph Library

Opened 12 years ago

Last modified 2 years ago

#296 assigned task

Multicommodity flow algorithms

Reported by: Peter Kovacs Owned by: Peter Kovacs
Priority: major Milestone:
Component: core Version: hg main
Keywords: Cc:
Revision id:


It would be important to implement various multicommodity flow algorithms in LEMON. Approximation (and maybe exact) solution methods for fractional, integral and unsplittable multicommodity flow problems.

Change History (3)

comment:1 Changed 12 years ago by Peter Kovacs

I'm working on approximation algorithms for the following (fractional) problems according to Garg, Könemann and Fleischer.

  • maximum multicommodity flow,
  • weighted maximum multicommodity flow,
  • maximum concurrent flow,
  • min. cost maximum concurrent flow.

The working repository of these algorithms can be found here:

comment:2 Changed 12 years ago by Peter Kovacs

Milestone: LEMON 1.2 release
Owner: changed from Alpar Juttner to Peter Kovacs
Status: newassigned

comment:3 Changed 12 years ago by Peter Kovacs

Type: enhancementtask
Note: See TracTickets for help on using tickets.