Tight bound for matching (vol 23, pg 322, 2012)

被引：0

作者：

Han, Yijie ^{[1
]}

机构：

[1] Univ Missouri, Sch Comp & Engn, Kansas City, MO 64110 USA

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2013年 / 26卷 / 02期

关键词：

Combinatorial problems; Graph algorithms; Matching; Lower bound;

D O I：

10.1007/s10878-012-9566-8

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

The bound on the size of maximum matching given in the paper as follows: M >= {m/2 - m/2L, if k = 2 m/k - m/(k + L)k, if k > 2 is not accurate. We now correct the bound to M >= m/k - m/Lk, where M is the size of the maximum matching in any graph of degree k, m edges and length of the smallest odd size cycle L. When no simple odd-length cycle exists it is known previously that M >= m/k. We show that the new bound given here is tight.

引用

页码：412 / 414

页数：3