Article ID Journal Published Year Pages File Type
4647081 Discrete Mathematics 2015 8 Pages PDF
Abstract
A graph G is equimatchable if all its maximal matchings are of the same cardinality. Assume that a weight function w is defined on the edges of G. Then G is w-equimatchable if all its maximal matchings are of the same weight. For every graph G, the set of weight functions w such that G is w-equimatchable is a vector space. We present an O(m⋅n4+n5logn) algorithm, which receives an input graph G, and outputs the vector space of weight functions w such that G is w-equimatchable.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,