Tight bounds on maximal and maximum matchings

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

doi:10.1007/3-540-45678-3_27

Tight bounds on maximal and maximum matchings

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

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Algorithms and Computation - 12th International Symposium, ISAAC 2001, Proceedings
Pages	308-319
Number of pages	12
DOIs	https://doi.org/10.1007/3-540-45678-3_27
State	Published - 2001
Event	12th International Symposium on Algorithms and Computation, ISAAC 2001 - Christchurch, New Zealand Duration: Dec 19 2001 → Dec 21 2001

Publication series

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

Other

Other	12th International Symposium on Algorithms and Computation, ISAAC 2001
Country/Territory	New Zealand
City	Christchurch
Period	12/19/01 → 12/21/01

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-45678-3_27

Cite this

Biedl, T., Demaine, E. D., Duncan, C. A., Fleischer, R., & Kobourov, S. G. (2001). Tight bounds on maximal and maximum matchings. In Algorithms and Computation - 12th International Symposium, ISAAC 2001, Proceedings (pp. 308-319). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2223 LNCS). https://doi.org/10.1007/3-540-45678-3_27

Tight bounds on maximal and maximum matchings. / Biedl, Therese; Demaine, Erik D.; Duncan, Christian A. et al.
Algorithms and Computation - 12th International Symposium, ISAAC 2001, Proceedings. 2001. p. 308-319 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2223 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Biedl, T, Demaine, ED, Duncan, CA, Fleischer, R & Kobourov, SG 2001, Tight bounds on maximal and maximum matchings. in Algorithms and Computation - 12th International Symposium, ISAAC 2001, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2223 LNCS, pp. 308-319, 12th International Symposium on Algorithms and Computation, ISAAC 2001, Christchurch, New Zealand, 12/19/01. https://doi.org/10.1007/3-540-45678-3_27

Biedl T, Demaine ED, Duncan CA, Fleischer R, Kobourov SG. Tight bounds on maximal and maximum matchings. In Algorithms and Computation - 12th International Symposium, ISAAC 2001, Proceedings. 2001. p. 308-319. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-45678-3_27

@inproceedings{bf6951feacb84aaaa19ff20ce942ed5d,

title = "Tight bounds on maximal and maximum matchings",

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.",

author = "Therese Biedl and Demaine, {Erik D.} and Duncan, {Christian A.} and Rudolf Fleischer and Kobourov, {Stephen G.}",

year = "2001",

doi = "10.1007/3-540-45678-3_27",

language = "English (US)",

isbn = "3540429859",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "308--319",

booktitle = "Algorithms and Computation - 12th International Symposium, ISAAC 2001, Proceedings",

note = "12th International Symposium on Algorithms and Computation, ISAAC 2001 ; Conference date: 19-12-2001 Through 21-12-2001",

}

TY - GEN

T1 - Tight bounds on maximal and maximum matchings

AU - Biedl, Therese

AU - Demaine, Erik D.

AU - Duncan, Christian A.

AU - Fleischer, Rudolf

AU - Kobourov, Stephen G.

PY - 2001

Y1 - 2001

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

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

UR - http://www.scopus.com/inward/record.url?scp=23044530598&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=23044530598&partnerID=8YFLogxK

U2 - 10.1007/3-540-45678-3_27

DO - 10.1007/3-540-45678-3_27

M3 - Conference contribution

AN - SCOPUS:23044530598

SN - 3540429859

SN - 9783540429852

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 308

EP - 319

BT - Algorithms and Computation - 12th International Symposium, ISAAC 2001, Proceedings

T2 - 12th International Symposium on Algorithms and Computation, ISAAC 2001

Y2 - 19 December 2001 through 21 December 2001

ER -

Tight bounds on maximal and maximum matchings

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this