Tight bounds on maximal and maximum matchings

Therese Biedl, Erik D. Demaine, Christian A. Duncan, Rudolf Fleischer, Stephen G. Kobourov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

In this paper, we study bounds on maximal and maximum matchings in special graph classes, speci.cally 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 graph within the class.

Original languageEnglish (US)
Title of host publicationAlgorithms and Computation - 12th International Symposium, ISAAC 2001, Proceedings
Pages308-319
Number of pages12
DOIs
StatePublished - 2001
Event12th International Symposium on Algorithms and Computation, ISAAC 2001 - Christchurch, New Zealand
Duration: Dec 19 2001Dec 21 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2223 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other12th International Symposium on Algorithms and Computation, ISAAC 2001
Country/TerritoryNew Zealand
CityChristchurch
Period12/19/0112/21/01

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Tight bounds on maximal and maximum matchings'. Together they form a unique fingerprint.

Cite this