Some Results On Rings And Trees Of Rings Loading Problem

Our thesis has three sections.in first section we discuss undirected rings and tree of rings loading problem,including the first and second chapter; In second section we discuss directed rings and tree of rings loading problem,including the third and forth chapter;in the third sections we put forward a polynomial time approximation scheme( PTAS)for the improved bi-directed ring loading problem, including the fifth chapter.A tree of rings G is an undirected graph obtained from a tree T by replacing each node of the tree T with a cycle (called tree-node cycle) and then contracting the edges of the tree so that two cycles corresponding to the two end-nodes of any edge have precisely one node in common and no three tree-node-cycles share a same node.(A more general definition may allow them to share the same node).[1]The problem is,given a set of demands D={d(i,j) I d(i,j)is nonnegative reals, i, j∈V(G)},each demand must be routed in a path in the tree of ring. In each ring, all of the demand between each pair of nodes must and can but be routed one of the two possible ways around the ring The object is to minimize the maximum load in the tree of ring,where the load of an edge is the sum of the demands routed through that edge. We provide a polynomial time approximation scheme( PTAS) to solve it. The main results about tree of rings loading problem are as follows: Algorithm2.1: Polynomial time approximation scheme for tree of rings loading problem.Theorem2.1: Algorithm2.1 is a Polynomial time approximation scheme Theorem2.2 When Algorithm2.1 end, the path between each node pairs which...