2013/05/23 by Alexander Bolshoy, Bolshoy, Alexander, Valery Kirzhner +1
Biochemistry, Genetics and Molecular Biology · Computer Science · Decision Sciences · #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Biological sciences #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #Multi-Criteria Decision Making #Populations and Evolution (q-bio.PE) #cs.DS #q-bio.PE
paper · pdf · doi:10.48550/arxiv.1305.5551
arxiv created 2013/05/23 · openalex publication_date 2013/05/23 · arxiv updated 2013/05/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Suppose we label the vertices of a tree by positive integers. The weight of an edge is defined by a monotonically increasing function of the absolute value of the difference of the labels of its endpoints. We define the total cost of the labeling to be the sum of weight of all the edges.The problem we consider is that of determining for a given tree G and given a labeling of the leaves of G the minimum total cost labellings of G. In this paper we present an algorithm that works for any cost function satisfies the condition of monotony mentioned above. In a case of the function defined as the absolute value of the difference of the labels the fast algorithm is presented.