Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1141826 | Discrete Optimization | 2006 | 5 Pages |
Abstract
In 1957 Berge [C. Berge, Two theorems in graph theory, Proceedings of the National Academy of Sciences 43 (1957) 842–844] established that a matching is maximum if and only if there are no augmenting paths in the graph. In this paper we prove Berge’s result for a generalization of the matching problem—the maximum charge problem with capacity constraints. We show that a charge is maximum if and only if there is no alternating path, or lasso, along which the charge can be augmented.
Related Topics
Physical Sciences and Engineering
Mathematics
Control and Optimization
Authors
Ramesh Krishnamurti, Daya Ram Gaur, Subir Kumar Ghosh, Horst Sachs,