Maintaining centdians in a fully dynamic forest with top trees

Hung Lung Wang*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)

Abstract

In this paper, we consider the problem of maintaining the centdians in a fully dynamic forest. A forest is said to be fully dynamic if edge insertions, edge deletions, and changes of vertex weights are allowed. Centdian is a specific kind of facility that integrates the notions of center and median by taking a convex combination on the objective functions of both problems. This work extends the results in Alstrup et al. [2] within the same time complexity, i.e., linear time preprocessing and O(logn) per update, where n is the number of vertices of the components being updated.

Original languageEnglish
Pages (from-to)310-315
Number of pages6
JournalDiscrete Applied Mathematics
Volume181
DOIs
Publication statusPublished - 2015 Jan 30
Externally publishedYes

Keywords

  • Centdian
  • Fully dynamic forest
  • Nonlocal search
  • Top tree

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Maintaining centdians in a fully dynamic forest with top trees'. Together they form a unique fingerprint.

Cite this