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 -