On matching cover of graphs
成果类型：
Article
署名作者：
Wang, Xiumei; Song, Xiaoxin; Yuan, Jinjiang
署名单位：
Zhengzhou University; Henan University
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-013-0731-3
发表日期：
2014
页码：
499-518
关键词：
摘要：
A k-matching cover of a graph is a union of matchings of which covers . The matching cover number of , denoted by , is the minimum number such that has a -matching cover. A matching cover of is optimal if it consists of matchings of . In this paper, we present an algorithm for finding an optimal matching cover of a graph on vertices in time (if use a faster maximum matching algorithm, the time complexity can be reduced to , where ), and give an upper bound on matching cover number of graphs. In particular, for trees, a linear-time algorithm is given, and as a by-product, the matching cover number of trees is determined.