Krishnamurti, Ramesh ; Gaur, Daya Ram ; Ghosh, Subir Kumar ; Sachs, Horst (2006) Berge's theorem for the maximum charge problem Discrete Optimization, 3 (2). pp. 174-178. ISSN 1572-5286
Full text not available from this repository.
Official URL: http://www.sciencedirect.com/science/article/pii/S...
Related URL: http://dx.doi.org/10.1016/j.disopt.2005.08.008
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.
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to Elsevier Science. |
| Keywords: | Matching; Augmenting Path; Fractional Matching |
| ID Code: | 76283 |
| Deposited On: | 31 Dec 2011 08:57 |
| Last Modified: | 31 Dec 2011 08:57 |
Repository Staff Only: item control page
