Strongly maximal matchings in infinite graphs

zbMATH Open1178.05072arXiv0911.4010MaRDI QIDQ1010872FDOQ1010872

Authors: Ron Aharoni, Eli Berger, Agelos Georgakopoulos, Philipp Sprüssel 

Publication date: 7 April 2009

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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 NM is at most the sum of weights of the edges in MN. We prove that if w assumes only finitely many values all of which are rational then G has a strongly w-maximal matching.

Full work available at URL: https://arxiv.org/abs/0911.4010

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Strong LP duality in weighted infinite bipartite graphs
• Maximum vertex-weighted matching in strongly chordal graphs
• Strong and weighted matchings in inhomogenous random graphs
• Infinite matching theory
• Matchings in infinite graphs

zbMATH Keywords

matchinginfinite graphstrongly weight maximal matchingweighted edges

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (2)

• Matchable infinite graphs
• Matchings in infinite graphs

This page was built for publication: Strongly maximal matchings in infinite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1010872)