summary |
shortlog |
changelog |
graph |
tags |
bookmarks |
branches |
files |
changeset |
file |
latest |
revisions |
annotate |
diff |
comparison |
raw |
help

doc/min_cost_flow.dox

changeset 1221 | 1c978b5bcc65 |

parent 1164 | f63ba40a60f4 |

child 1270 | dceba191c00d |

equal
deleted
inserted
replaced

6:435946b36771 | 7:75e70d7b0995 |
---|---|

24 \section mcf_def Definition (GEQ form) |
24 \section mcf_def Definition (GEQ form) |

25 |
25 |

26 The \e minimum \e cost \e flow \e problem is to find a feasible flow of |
26 The \e minimum \e cost \e flow \e problem is to find a feasible flow of |

27 minimum total cost from a set of supply nodes to a set of demand nodes |
27 minimum total cost from a set of supply nodes to a set of demand nodes |

28 in a network with capacity constraints (lower and upper bounds) |
28 in a network with capacity constraints (lower and upper bounds) |

29 and arc costs \ref amo93networkflows. |
29 and arc costs \cite amo93networkflows. |

30 |
30 |

31 Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$, |
31 Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$, |

32 \f$upper: A\rightarrow\mathbf{R}\cup\{+\infty\}\f$ denote the lower and |
32 \f$upper: A\rightarrow\mathbf{R}\cup\{+\infty\}\f$ denote the lower and |

33 upper bounds for the flow values on the arcs, for which |
33 upper bounds for the flow values on the arcs, for which |

34 \f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$, |
34 \f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$, |