ABSTRACT
This chapter aims to study procedures for solving both the cardinality matching problem and the weighted matching problem in an arbitrary undirected graph. The stable marriage problem is the problem of finding a stable matching for an arbitrary preference matrix. The constructive proof of Theorem gives an iterative algorithm to solve this problem. The matching which results from this ‘propose-and-reject’ algorithm is not only stable but also optimal. The Chinese postman problem is concerned with situations of the following type: a postman starts from the post office with mail for delivery and delivers it on his beat, covering each street at least once before returning to the post office. It is assumed that while traversing a street in one direction he delivers mail to addresses on both sides of the street by crossing the street back and forth as many times as necessary.
