The cent-dian path problem on tree networks

Ronald I. Becker, Yen I. Chiang, Isabella Lari, Andrea Scozzari

研究成果: 圖書/報告稿件的類型會議稿件同行評審

5 引文 斯高帕斯(Scopus)

摘要

In a network, the distsum of a path is the sum of the distances of all vertices to the path, and the eccentricity is the maximum distance of any vertex to the path. The Cent-dian problem is the constrained optimization problem which seeks to locate on a network a path which has minimalv alue of the distsum over all paths whose eccentricity is bounded by a fixed constant. We consider this problem for trees, and we also consider the problem where an additional constraint is required, namely that the optimal path has length bounded by a fixed constant. The first problem has already been considered in the literature. We give another linear time algorithm for this problem which is considerably simpler than the previous one. The second problem does not seem to have been considered elsewhere, and we give an O(n log2 n) divide-and-conquer algorithm for its solution.

原文英語
主出版物標題Algorithms and Computation - 12th International Symposium, ISAAC 2001, Proceedings
頁面743-755
頁數13
DOIs
出版狀態已出版 - 2001
對外發佈
事件12th International Symposium on Algorithms and Computation, ISAAC 2001 - Christchurch, 新西蘭
持續時間: 19 12 200121 12 2001

出版系列

名字Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
2223 LNCS
ISSN(列印)0302-9743
ISSN(電子)1611-3349

Conference

Conference12th International Symposium on Algorithms and Computation, ISAAC 2001
國家/地區新西蘭
城市Christchurch
期間19/12/0121/12/01

指紋

深入研究「The cent-dian path problem on tree networks」主題。共同形成了獨特的指紋。

引用此