Berge’s theorem for the maximum charge problem

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 probl...

Full description

Saved in:
Bibliographic Details
Published in:Discrete optimization 2006-06, Vol.3 (2), p.174-178
Main Authors: Krishnamurti, Ramesh, Ram Gaur, Daya, Ghosh, Subir Kumar, Sachs, Horst
Format: Article
Language:English
Subjects:
Augmenting path
Fractional matching
Matching
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1572-5286
1873-636X
DOI:10.1016/j.disopt.2005.08.008