Finding Cores of Limited Length

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

Finding Cores of Limited Length

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

Research output: Book / Anthology / Report / Ph.D. thesis › Report › Research

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(n³) due to minieka (networks, 1985)

Original language	English

Place of Publication	Copenhagen
Publisher	IT-Universitetet i København
Edition	TR-2000-4
Number of pages	21
ISBN (Electronic)	87-7949-007-7
Publication status	Published - Jul 2001
Externally published	Yes

Series	IT University Technical Report Series
Number	TR-2000-4
ISSN	1600-6100

Access to Document

ITU-TR-2001-4 pdfFinal published version, 290 KB

Cite this

@book{b2332a926cf14ff09a3e805b2157cae8,

title = "Finding Cores of Limited Length",

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)",

author = "Stephen Alstrup and Mikkel Thorup and Lauridsen, {Peter W.} and Peer Sommerlund",

year = "2001",

month = jul,

language = "English",

series = "IT University Technical Report Series",

number = "TR-2000-4",

publisher = "IT-Universitetet i K{\o}benhavn",

address = "Denmark",

edition = "TR-2000-4",

}

TY - RPRT

T1 - Finding Cores of Limited Length

AU - Alstrup, Stephen

AU - Thorup, Mikkel

AU - Lauridsen, Peter W.

AU - Sommerlund, Peer

PY - 2001/7

Y1 - 2001/7

N2 - 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)

AB - 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)

M3 - Report

T3 - IT University Technical Report Series

BT - Finding Cores of Limited Length

PB - IT-Universitetet i København

CY - Copenhagen

ER -

Finding Cores of Limited Length

Abstract

Access to Document

Fingerprint

Cite this