Tight bounds on maximal and maximum matchings

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

doi:10.1016/j.disc.2004.05.003

Tight bounds on maximal and maximum matchings

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

Computer Science

Research output: Contribution to journal › Article › peer-review

70 Scopus citations

Abstract

In this paper, we study lower bounds on the size of maximal and maximum matchings in 3-connected planar graphs and graphs with bounded maximum degree. For each class, we give a lower bound on the size of matchings, and show that the bound is tight for some graph within the class.

Original language	English (US)
Pages (from-to)	7-15
Number of pages	9
Journal	Discrete Mathematics
Volume	285
Issue number	1-3
DOIs	https://doi.org/10.1016/j.disc.2004.05.003
State	Published - Aug 6 2004

Keywords

Bounded maximum degree
Bounds
Matching
Planar graphs

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2004.05.003

Cite this

@article{2411645a2ce740659a9ac1b3fbc34b33,

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

abstract = "In this paper, we study lower bounds on the size of maximal and maximum matchings in 3-connected planar graphs and graphs with bounded maximum degree. For each class, we give a lower bound on the size of matchings, and show that the bound is tight for some graph within the class.",

keywords = "Bounded maximum degree, Bounds, Matching, Planar graphs",

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

year = "2004",

month = aug,

day = "6",

doi = "10.1016/j.disc.2004.05.003",

language = "English (US)",

volume = "285",

pages = "7--15",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "1-3",

}

TY - JOUR

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 - 2004/8/6

Y1 - 2004/8/6

N2 - In this paper, we study lower bounds on the size of maximal and maximum matchings in 3-connected planar graphs and graphs with bounded maximum degree. For each class, we give a lower bound on the size of matchings, and show that the bound is tight for some graph within the class.

AB - In this paper, we study lower bounds on the size of maximal and maximum matchings in 3-connected planar graphs and graphs with bounded maximum degree. For each class, we give a lower bound on the size of matchings, and show that the bound is tight for some graph within the class.

KW - Bounded maximum degree

KW - Bounds

KW - Matching

KW - Planar graphs

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

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

U2 - 10.1016/j.disc.2004.05.003

DO - 10.1016/j.disc.2004.05.003

M3 - Article

AN - SCOPUS:3142607299

SN - 0012-365X

VL - 285

SP - 7

EP - 15

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

Tight bounds on maximal and maximum matchings

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this