Paper by Erik D. Demaine

Reference:

Therese Biedl, Erik D. Demaine, Christian A. Duncan, Rudolf Fleischer, and Stephen G. Kobourov, “Tight Bounds on Maximal and Maximum Matchings”, in Proceedings of the 12th Annual International Symposium on Algorithms and Computation (ISAAC 2001), Lecture Notes in Computer Science, volume 2223, Christchurch, New Zealand, December 19–21, 2001, pages 308–319.

Abstract:

In this paper, we study bounds on maximal and maximum matchings in special graph classes, specifically triangulated graphs and graphs with bounded maximum degree. For each class, we give a lower bound on the size of matchings, and prove that it is tight for some graphs within the class.

Comments:

This paper is also available from the electronic LNCS volume as http://link.springer.de/link/service/series/0558/papers/2223/22230308.pdf.

Copyright:

The paper is \copyright Springer-Verlag.

Length:

The paper is 12 pages.

Availability:

The paper is available in PostScript (166k) and gzipped PostScript (52k).

See information on file formats.

[Google Scholar search]

Related papers:

MatchingBounds_DM (Tight Bounds on Maximal and Maximum Matchings)

MatchingJAlgorithms (Efficient Algorithms for Petersen's Matching Theorem)