Minimum costK-forest covers |
| |
| Authors: | Sjoerd M Baas Jorge Orestes Cerdeira |
| |
| Institution: | (1) Faculty of Applied Mathematics, University of Twente, 7500 AE Enschede, the Netherlands;(2) Instituto Superior de Agronomia, Tapada da Ajuda, 1399, Lisboa Codex, Portugal |
| |
| Abstract: | A forest cover of a graph is a spanning forest for which each component has at least two nodes. IfK is a subset of nodes, aK-forest cover is a forest cover including exactly one node fromK in each component. AK-forest cover is of minimum cost if the sum of the costs of the edges is minimum. We present an0(n
2 + ¦K¦2
n) algorithm for determining the minimum costK-forest cover of a graph withn nodes. We show that the algorithm can also be used to determine, in0(n
2 + ({K — K'¦ + 
deK'd
v
)2
n
) time, the minimum costK-forest cover having degree equald
v
each nodev of an arbitrary subsetK' ofK. |
| |
| Keywords: | Forests covers spanning trees matchings |
| 本文献已被 SpringerLink 等数据库收录！ |
|
