Skip to search boxSkip to navigationSkip to main content

Finding Cores of Limited Length

  • Stephen Alstrup
    ,
  • Mikkel Thorup
    ,
  • Peter W. Lauridsen
    ,
  • Peer Sommerlund
  • AT&T
    ,
  • Maconomy
    ,
  • Netman ApS
Research Output:
Book / Anthology / Report
Report

Open access

Publication Information

Output type

Research Output:
Book / Anthology / Report
Report

Original language

English

Publication milestones

  • Published - 07/2001

Publication status

Published - 07/2001

Place of publication

Copenhagen

Edition

TR-2000-4

Publisher

IT-Universitetet i København, Denmark

Book series

  • Book series name: IT University Technical Report Series
    Series number: TR-2000-4
    ISSN: 1600-6100

ISBN (Electronic)

87-7949-007-7

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)

Access to documents

ITU-TR-2001-4 pdf, opens in new tab
Final published version, 290.35 KB