Research Reports from the Department of Operations
Document Type
Dissertation
Publication Date
7-1-1975
Abstract
The design of optimal networks on a set of points is an interesting and important problem. However, the majority of work done so far is in flow problems and on graphs with arc weights. In this dissertation, the problem of constructing optimal networks with node weights is considered. The objective function depends on the weights assigned to the nodes and the degree of the nodes. Special cases of the general design problem of constructing networks or graphs with node weights and arc weights are also treated. The intent of the research was to develop polynomially bounded algorithms. The general design problem is solved by polynomially bounded methods for the case when the objective function depends on the weights assigned to the nodes and is linear with respect to the degree of the nodes. The design of the undirected spanning tree, when the objective function is non-linear (monotone non-decreasing) with respect to the degree of nodes, is solved by a dynamic programming-type algorithm. A modification of this algorithm for a special case of degree functions reduces computational effort considerably. The design problem of simple graphs, when the objective function is separable and convex with respect to the degrees of the nodes, is shown to fall into the class of generalized matching problems, for which polynomial methods of solution already exist.
Keywords
Operations research, Graph theory, Algorithms, Dynamic programming, Convex functions, Mathematical optimization, Trees (Graph theory), Matching theory
Publication Title
Dissertation/Technical Memorandums from the Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 377 ; 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
Mehta, Shailesh J., "Optimal Design of Networks with Node Weighted Functions" (1975). Research Reports from the Department of Operations. 385.
https://commons.case.edu/wsom-ops-reports/385