Finding a core of a tree with pos/neg weight |
| |
Authors: | Mehdi Zaferanieh Jafar Fathali |
| |
Institution: | 1. Department of Mathematics, Hakim Sabzevari University, Tovhid town, Sabzevar, Iran 2. Department of Mathematics, Shahrood University of Technology, University Blvd., Shahrood, Iran
|
| |
Abstract: | Let T?=?(V, E) be a tree. A core of T is a path P, for which the sum of the weighted distances from all vertices to this path is minimized. In this paper, we consider the semi-obnoxious case in which the vertices have positive or negative weights. We prove that, when the sum of the weights of vertices is negative, the core must be a single vertex and that, when the sum of the vertices?? weights is zero there exists a core that is a vertex. Morgan and Slater (J Algorithms 1:247?C258, 1980) presented a linear time algorithm to find the core of a tree with only positive weights of vertices. We show that their algorithm also works for semi-obnoxious problems. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|