Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647081 | Discrete Mathematics | 2015 | 8 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Vadim E. Levit, David Tankus,