Paper Info
Title
A linear algorithm for the number of degree constrained subforests of a tree
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.
Year
DOI
Venue
1982
10.1016/0020-0190(82)90103-X
Information Processing Letters
Keywords
Field
DocType
Tree,path cover,spanning subforest,b-matching,endvertex list (postorder numbering)
Discrete mathematics,Combinatorics,Minimum degree spanning tree,Prim's algorithm,k-minimum spanning tree,Neighbourhood (graph theory),Spanning tree,Shortest-path tree,Mathematics,Kruskal's algorithm,Minimum spanning tree
Journal
Volume
Issue
ISSN
15
4
0020-0190
Citations 
PageRank 
References 
0
0.34
3
Authors
1
Name
Order
Citations
PageRank
Peter J. Slater1593132.02