Finding a core of a tree with pos/neg weight

Finding a core of a tree with pos/neg weight

0.00 Avg rating0 Votes
Article ID: iaor20125890
Volume: 76
Issue: 2
Start Page Number: 147
End Page Number: 160
Publication Date: Oct 2012
Journal: Mathematical Methods of Operations Research
Authors: ,
Keywords: optimization
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 (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.

Reviews

Required fields are marked *. Your email address will not be published.