Finding Cores of Limited Length

Stephen Alstrup, Mikkel Thorup, Peter W. Lauridsen, Peer Sommerlund

Publikation: Bog / Antologi / Rapport / Ph.D.-afhandlingRapportForskning

Abstract

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)
OriginalsprogEngelsk
UdgivelsesstedCopenhagen
ForlagIT-Universitetet i København
UdgaveTR-2000-4
Antal sider21
ISBN (Elektronisk)87-7949-007-7
StatusUdgivet - jul. 2001
Udgivet eksterntJa
NavnIT University Technical Report Series
NummerTR-2000-4
ISSN1600-6100

Fingeraftryk

Dyk ned i forskningsemnerne om 'Finding Cores of Limited Length'. Sammen danner de et unikt fingeraftryk.

Citationsformater