Admissible transformations and their applications to matching problems

Research output: Chapter in Book/Report/Conference proceedingChapter


For special combinatorial optimization problems different kind of objective functions as for instance the classical sum objective or the bottleneck objective are of practical interest. Mostly these objective functions are treated separately and independently. The introduction of an “algebraic objective function” the cost coefficients of which are elements of an ordered commutative semigroup allows a unified treatment. For standard problems like shortest path, matching and matroid intersection problems this approach has led to efficient algorithms for a broad class of objective functions. One specific type of algorithm is based on transformations of the cost coefficients and on a purely combinatorial motivated optimality criterion. We will introduce this principle of “admissible transformations” for the general combinatorial optimization problem with algebraic objective. Then we demonstrate how this general principle combined with some problem specific combinatorial observations leads to efficient and transparent algorithms for the problem of finding an optimal perfect matching.
Original languageEnglish
Title of host publicationStudies on graphs and discrete programming
Place of PublicationNorth Holand, Amesterdam
Publication statusPublished - 1981
Externally publishedYes

Publication series

NameNorth-Holland Mathematics Studies
ISSN (Electronic)0304-0208


Dive into the research topics of 'Admissible transformations and their applications to matching problems'. Together they form a unique fingerprint.

Cite this