Maintaining centdians in a fully dynamic forest with top trees

Hung Lung Wang*

*此作品的通信作者

研究成果: 雜誌貢獻期刊論文同行評審

1 引文 斯高帕斯(Scopus)

摘要

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.

原文英語
頁(從 - 到)310-315
頁數6
期刊Discrete Applied Mathematics
181
DOIs
出版狀態已發佈 - 2015 一月 30
對外發佈

ASJC Scopus subject areas

  • 離散數學和組合
  • 應用數學

指紋

深入研究「Maintaining centdians in a fully dynamic forest with top trees」主題。共同形成了獨特的指紋。

引用此