A polynomial algorithm for b-matchings: An alternative approach
type: Item
instance of: scholarly article
title: A polynomial algorithm for b-matchings: An alternative approach
zbMATH Open document ID: 0655.90090
DOI: 10.1016/0020-0190(87)90178-5
published in: Information Processing Letters
publication date: 1987-01-01T00:00:00Z
review text: A b-matching of a given graph G is an assignment of integer weights to the edges of G so that the sum of the weights on the edges incident with a vertex v is at most \(b_ v\) (b denotes the vectors of \(b_ v's)\). When \(b_ v=1\) for all vertices v in G, then b-matchings are the usual matchings. The b-matching problem asks for a b-matching of maximum cost where the edges of G have been assigned costs and the cost of a b- matching is the sum of the weights times the costs. We do not assume G to be bipartite. We present a polynomial algorithm for the b-matching problem differing from the algorithm of \textit{W. H. Cunningham} and \textit{A. B. Marsh} [Math. Program. Study 8, 50-72 (1978; Zbl 0409.90081)]. In fact, the new algorithm is strongly polynomial using the new strongly polynomial minimum cost flow algorithm of \textit{E. Tardos} [Combinatorica 5, 247-255 (1985; Zbl 0596.90030)] (we actually use the algorithm of \textit{J. B. Orlin} [``Genuinely polynomial simplex and nonsimplex algorithms for the minimum cost flow problem'', Centrum for Wiskunde en Informatica, Stichting Mathematisch Centrum OS, No.8504 (1985)]) to obtain a half- integral optimal solution. An integral solution (close to being optimal) is obtained from it which is used as input to the b-matching algorithm of \textit{W. R. Pulleyblank} [``Faces of matching polyhedra'', Ph. D. Thesis, Dept. of Combinatorics and Optimization, Univ. of Waterloo (1973)].
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 90C27
zbMATH DE Number: 4070668
zbMATH Keywords: half-integer solution
zbMATH Keywords: b-matching
zbMATH Keywords: assignment of integer weights to the edges
zbMATH Keywords: polynomial algorithm
zbMATH Keywords: half-integral optimal solution
author: R. P. Anstee
MaRDI profile type: Publication
full work available at URL: 0020-0190(87)90178-5
OpenAlex ID: W2005633226
cites work: An algorithmic proof of Tutte's f-factor theorem
cites work: Exceptional Paper—Design and Implementation of Large Scale Primal Transshipment Algorithms
cites work: Paths, Trees, and Flowers
cites work: Maximum matching and a polyhedron with 0,1-vertices
cites work: Q5675543
cites work: Some Properties of Graphs with Multiple Edges
cites work: A good algorithm for smallest spanning trees with a degree constraint
cites work: Q3048571
cites work: Q4080661
cites work: A strongly polynomial minimum cost circulation algorithm
Recommended article: Q3646847
Recommended article: An efficient algorithm for the bipartite matching problem
Recommended article: Q4871086
Recommended article: Bipartite perfect matching as a real polynomial
Recommended article: Q4264549
Recommended article: A polynomial algorithm for the extendability problem in bipartite graphs
Recommended article: A polyhedral approach to online bipartite matching
Recommended article: A Polyhedral Approach to Online Bipartite Matching
Recommended article: Q4474103
description: scientific article; zbMATH DE number 4070668