Article ID: | iaor20012482 |
Country: | United Kingdom |
Volume: | 6 |
Issue: | 6 |
Start Page Number: | 607 |
End Page Number: | 622 |
Publication Date: | Nov 1999 |
Journal: | International Transactions in Operational Research |
Authors: | Paschos Vangelis Th., Alfandari Laurent |
Keywords: | minimum spanning tree |
We prove that the problem of finding, in an undirected graph with non-negative costs on edges, a minimum cost rooted spanning tree of depth 2 is NP-hard. We then prove that, in a graph of order