Example and Experimental Results

In this chapter, we consider an example of multi-stage and bi-criteria optimization of matchings for a tree with five nodes [1, 2]. We also discuss the results of computational experiments with the algorithms \(\mathscr {A}_{5}\), \(\mathscr {A}_{6}\), and \(\mathscr {A}_{8}\) for randomly generated trees and weight functions. We compare the number of matchings before and after optimization, compare the maximum cardinality of matchings before and after optimization relative to a randomly generated weight function, consider the number of POPs for bi-criteria optimization of matchings relative to the cardinality and a weight function, and study the existence of totally optimal matchings.