An extended partitioning technique to transform trees into single-row networks

• We model a transformation technique to transform a tree graph into single-row network.
• The properties of an arbitrary graph and its relation to a single-row network were studied.
• We report the fundamental concepts for optimal single-row transformation of a tree.
• Single-row transformation enables the assignment of telephone channels to each caller-receiver pair in cellular network.

In this paper, we present a Tree Sequence Model (TSM) that transforms a tree into a single-row network. This transformation provides a working model for real-time channel assignment problems, such as the assignment of telephone channels to caller-receiver pairs in a cellular network. Each caller-receiver pair represents two nodes in a graph and the connection between each pair forms an edge of this graph. This tree graph is transformed into its corresponding single-row network to enable the assignment of telephone channels to each caller-receiver pair. TSM begins with the formation of partitions from the tree and the formation of zones from these partitions through an insertion mechanism. This process is followed by the formation of terminals and intervals using Enhanced Simulated Annealing for Single-Row Routing (ESSR) to optimize the transformation of nets into single-row networks. Experimental results show that the TSM can optimally and efficiently transform all types of trees into single-row networks.

Figure optionsDownload as PowerPoint slide