𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Solving the undirected minimum cost flow problem with arbitrary costs

✍ Scribed by A. Sedeño-Noda; C. González-Martín; S. Alonso

Publisher
John Wiley and Sons
Year
2004
Tongue
English
Weight
66 KB
Volume
45
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We address the undirected minimum cost flow problem with arbitrary arcs costs. Any optimal solution for this problem is characterized by the property that the flow of each arc with negative cost must be equal to its capacity. That is, the flow can be nonzero in both directions. This situation implies that the flow can take values that are integer multiple of ½. Therefore, this single commodity flow problem does not satisfy the unimodularity property. However, using a reformulation of the original problem, we develop an easy method for solving it using any classical minimum‐cost flow problem algorithm. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 45(1), 1–3 2005

📜 SIMILAR VOLUMES

Models and heuristics for the k -degree
Models and heuristics for the k -degree constrained minimum spanning tree problem with node-degree costs
✍ Christophe Duhamel; Luís Gouveia; Pedro Moura; Maurício de Souza 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 319 KB 👁 1 views

## Abstract The __k__ ‐Degree constrained Minimum Spanning Tree Problem (__k__ ‐DMSTP) consists in finding a minimal cost spanning tree satisfying the condition that every node has a degree no greater than a fixed value __k__. Here we consider an extension where besides the edge costs, a concave co