Linear-time heuristic partitioning technique for mapping of connected graphs into single-row networks

Abstract

In this paper, a model called graph partitioning and transformation model (GPTM) which transforms a connected graph into a single-row network is introduced. The transformation is necessary in applications such as in the assignment of telephone channels to caller-receiver pairs roaming in cells in a cellular network on real-time basis. A connected graph is then transformed into its corresponding single-row network for assigning the channels to the caller-receiver pairs. The GPTM starts with the linear-time heuristic graph partitioning to produce two subgraphs with higher densities. The optimal labeling for nodes are then formed based on the simulated annealing technique. Experimental results support our hypothesis that GPTM efficiently transforms the connected graph into its single-row network.