In this paper we consider several well-studied variants of the problem of finding a core if a prescribed length in a tree. Here a core is a path minimizing the sum of the distance to all nodes in the tree. Our most general result is an O(n log n a(n)) algorithm for the case with weighted tree edges. The previous best bound was O(n3) due to minieka (networks, 1985)
Udgivelsessted | Copenhagen |
---|
Forlag | IT-Universitetet i København |
---|
Udgave | TR-2000-4 |
---|
Antal sider | 21 |
---|
ISBN (Elektronisk) | 87-7949-007-7 |
---|
Status | Udgivet - jul. 2001 |
---|
Udgivet eksternt | Ja |
---|
Navn | IT University Technical Report Series |
---|
Nummer | TR-2000-4 |
---|
ISSN | 1600-6100 |
---|