A linear algorithm for the number of degree constrained subforests of a tree |
| |
Authors: | Peter J Slater |
| |
Affiliation: | Mathematics Department, University of Alabama, Hunstville, AL 35899, U.S.A. |
| |
Abstract: | Recent work of Farrell is concerned with determining the total number of ways in which one can cover the vertices of a tree T with vertex disjoint paths. Such path covers are spanning subforests in which each vertex is restricted to have degree at most two. If b: V(T)→N is a positive integer-valued function, then finding a b-matching is equivalent to finding a spanning subgraph in which the degree of each vertex v is at most b(v). A linear-time algorithm for determining the number of b-matching in a tree is presented. |
| |
Keywords: | Tree path cover spanning subforest b-matching endvertex list (postorder numbering) |
本文献已被 ScienceDirect 等数据库收录! |