The obnoxious center problem on a tree

作     者：Burkard, RE Dollani, H Lin, YX Rote, G 

作者机构：Graz Tech Univ Inst Math A-8010 Graz Austria Zhengzhou Univ Dept Math Zhengzhou 450052 Peoples R China Free Univ Berlin Inst Informat D-14195 Berlin Germany 

出 版 物：《SIAM JOURNAL ON DISCRETE MATHEMATICS》 (工业与应用数学会离散数学杂志)

年 卷 期：2001年第14卷第4期

页      面：498-509页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：location problems center problem obnoxious facilities linear-time algorithm 

摘      要：The obnoxious center problem in a graph G asks for a location on an edge of the graph such that the minimum weighted distance from this point to a vertex of the graph is as large as possible. We derive algorithms with linear running time for the cases when G is a path or a star, thus improving previous results of Tamir [SIAM J. Discrete Math, 1 (1988), pp. 377-396]. For subdivided stars we present an algorithm of running time O (n log n). For general trees, we improve an algorithm of Tamir [SIAM J. Discrete Math, 1 (1988), pp. 377-396] by a factor of log n. Moreover, a linear algorithm for the unweighted center problem on an arbitrary tree with neutral and obnoxious vertices is described.