Research Reports from the Department of Operations
Document Type
Dissertation
Publication Date
6-1-1976
Abstract
Consider the problem of labeling the nodes of a given tree on n nodes with labels 1,2,...,n. Let d(i,i+1) be the number of edges in the path from node labeled i to node labeled i+1, i=1,2,...,n. d(n,n+1) is considered as d(n,1). The sum of d(i,i+1) over i=1,2,.. .,n is the quantity, call it SL' of interest. The minimum of SL is 2(n-1) for any tree on n nodes. This result is established and an efficient algorithm is given to achieve this value. This result is extended to trees having non-negative edge lengths. Since this problem can also be considered as a traveling salesman il problem, the problem of identifying a given symmetric distance traveling salesman problem is also considered. If the given matrix satisfies the conditions given in a theorem, then the traveling salesman problem can be solved exactly. On the other hand, the result on trees can still be used to get "good" solutions to the problem, under certain weak conditions. As an example, a wellknown problem on 42 cities is solved within 6% of the optimal solution by using the result on trees. Next, the problem of maximizing SL is considered and an efficient algorithm is given to achieve the maximum of SL. The maximum of SL depends on the structure of the tree and the algorithm uses the structure of the tree through a quantity called "usage number of an edge" which is the maximum number of times an edge can be used. Through the algorithm it is established that the "chain" structure has the highest value for SL and the "star" the lowest. Suppose Wl'w2'...'wn are given non-negative numbers and we wish to minimize the sum of Wid(i,i+1) over i=l,2, . . . ,r l. This "weighted path length" problem seems to be a hard one to solve by a "good" algorithm. However, tight bounds are derived using the structure of the tree and a heuristic algorithm based on the maximum number of l's achievable in a path vector (which is a 2-matching problem) is suggested and it is shown that the heuristic obtains a solution within the tight bounds derived earlier. Finally, some preliminary results on characterizing the convex hull of the path vectors by a set of linear constraints are given.
Keywords
Operations research, Trees (Graph theory), Graph theory, Algorithms, Mathematical optimization, Traveling salesman problem, Path analysis (Statistics), Combinatorial optimization
Publication Title
Dissertation/Technical Memorandums from the Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 400 ; Submitted in partial fulfillment of the requirements for the Degree of Doctor of Philosophy.
Rights
This work is in the public domain and may be freely downloaded for personal or academic use
Recommended Citation
Rao, Raghavendra N., "Optimal Labeling on Trees" (1976). Research Reports from the Department of Operations. 392.
https://commons.case.edu/wsom-ops-reports/392