Back to Search Start Over

Strongly maximal matchings in infinite weighted graphs

Authors :
Aharoni, Ron
Berger, Eli
Georgakopoulos, Agelos
Sprüssel, Philipp
Source :
Electronic Journal of Combinatorics 15 (2008), #R136
Publication Year :
2009

Abstract

Given an assignment of weights w to the edges of a graph G, a matching M in G is called strongly w-maximal if for any matching N the sum of weights of the edges in N\M is at most the sum of weights of the edges in M\N. We prove that if w assumes only finitely many values all of which are rational then G has a strongly w-maximal matching.<br />Comment: 17 pages

Details

Database :
arXiv
Journal :
Electronic Journal of Combinatorics 15 (2008), #R136
Publication Type :
Report
Accession number :
edsarx.0911.4010
Document Type :
Working Paper