A Linear Algorithm to Find the Maximum-weighted Matching in Halin Graphs.

Finding a matching with the maximum total weight is the well-known assignment problem of assigning people to jobs and maximize the profits. In this paper, we focus on finding the maximum-weighted matching in Halin graphs. First, we review the method of "shrinking fan". Second, we show how to use the method in finding the maximum-weighted matching in Halin graphs and then a linear algorithm is designed to solve this problem. Finally, it is shown that the algorithm can be easily extended to solve many relative problems. [ABSTRACT FROM AUTHOR]