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.

BibTeX

@InProceedings{MatchingBounds_ISAAC2001,
  AUTHOR        = {Therese Biedl and Erik D. Demaine and Christian A. Duncan
                   and Rudolf Fleischer and Stephen G. Kobourov},
  TITLE         = {Tight Bounds on Maximal and Maximum Matchings},
  BOOKTITLE     = {Proceedings of the 12th Annual International Symposium on
                   Algorithms and Computation (ISAAC 2001)},
  ADDRESS       = {Christchurch, New Zealand},
  SERIES        = {Lecture Notes in Computer Science},
  SERIESURL     = {http://www.springer.de/comp/lncs/},
  VOLUME        = 2223,
  MONTH         = {December 19--21},
  YEAR          = 2001,
  PAGES         = {308--319},

  LENGTH        = {12 pages},
  PAPERS        = {MatchingBounds_DM; MatchingJAlgorithms},
  COPYRIGHT     = {The paper is \copyright Springer-Verlag.},
  doi           = {https://dx.doi.org/10.1007/3-540-45678-3_27},
  dblp          = {https://dblp.org/rec/conf/isaac/BiedlDDFK01},
  COMMENTS      = {This paper is also available from <A HREF="https://doi.org/10.1007/3-540-45678-3_27">SpringerLink</A>.},
}

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 SpringerLink.

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)