标题:A SIMPLE EXISTENCE CRITERION FOR (G LESS-THAN F)-FACTORS
作者:HEINRICH, K; HELL, P; KIRKPATRICK, DG; LIU, GZ
作者机构:[HEINRICH, K; HELL, P; KIRKPATRICK, DG; LIU, GZ]UNIV BRITISH COLUMBIA,DEPT COMP SCI,VANCOUVER V6T 1W5,BC,CANADA.;[HEINRICH, K; HELL, P; KIRK 更多
通讯作者:HEINRICH, K
通讯作者地址:[HEINRICH, K]SIMON FRASER UNIV,DEPT MATH & STAT,BURNABY V5A 1S6,BC,CANADA.
来源:DISCRETE MATHEMATICS
出版年:1990
卷:85
期:3
页码:313-317
DOI:10.1016/0012-365X(90)90387-W
摘要:We simplify the criterion of Lovasz for the existence of a (g,f)-factor when g < f, or when the graph is bipartite. Moreover, we give a simple direct proof, implying an O(square-root (g(V)).\E\) algorithm, for these cases. We then illustrate the convenience of the new criterion by deriving some old and some new facts about (g,f)-factors and [a,b]-factors.
收录类别:SCIE
WOS核心被引频次:21
资源类型:期刊论文
TOP