Sains Malaysiana 43(8)(2014): 1263-1269

Linear-Time Heuristic Partitioning Technique for Mapping of

Connected Graphs into Single-Row Networks

(Teknik Pemetakan Heuristik Masa-Linear untuk Pemetaan Graf Berkait kepada

Rangkaian Baris Tunggal)

Ser Lee Loh¹, Shaharuddin Salleh² & Nor Haniza Sarmin³*

¹Department of Industrial Power, Faculty of Electrical Engineering, Universiti Teknikal Malaysia Melaka, 76100 Durian Tunggal, Melaka, Malaysia

²Center for Industrial and Applied Mathematics, Universiti Teknologi Malaysia, 81310 Johor Bahru, Johor, Malaysia

³Department of Mathematical Sciences, Universiti Teknologi Malaysia, 81310 Johor Bahru, Johor, Malaysia

Diserahkan: 13 November 2011/Diterima: 18 November 2013

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.

Keywords: Connected graph; graph partitioning; single-row; transformation

ABSTRAK

Dalam kertas kajian ini, suatu model yang dinamakan model pembahagian graf dan transformasi (GPTM) yang mengubah suatu graf berkait kepada rangkaian baris tunggal diperkenalkan. Transformasi tersebut diperlukan dalam aplikasi seperti penugasan saluran telefon kepada pasangan pemanggil-penerima merayau dalam sel dalam rangkaian selular atas asas masa sebenar. Suatu graf berkait kemudiannya diubah kepada rangkaian baris tunggal yang sepadan untuk pengagihan saluran kepada pasangan pemanggil dan penerima. GPTM bermula dengan pembahagian graf kepada dua subgraf berketumpatan lebih tinggi. Pelabelan optimum untuk nod kemudiannya dibentuk berdasarkan teknik simulasi penyepuhlindapan. Hasil uji kaji menyokong hipotesis ini bahawa GPTM mengubah graf berkait kepada rangkaian baris tunggal dengan cekap.

Kata kunci: Baris tunggal; graf berkait; pembahagian graf; transformasi

RUJUKAN

Bhattacharya, B.B., Deogun, J.S. & Sherwani, N.A. 1988. A graph theoretic approach to single row routing problems. In Proceedings of the 1988 IEEE International Symposium on Circuit and Systems 2: 1437-1440. 

Fiduccia, C.M. & Mattheyses, R.M. 1982. A linear-time heuristic for improving network partitions. In Proc. 19th ACM/IEEE Design Automation Conference 175-181.

Kernighan, B.W. & Lin, S. 1970. An efficient heuristic procedure for partitioning graphs. Bell Sys. Tech. J. 49: 291-308.

Kirkpatrick, S., Gelatt, C.D. & Vecchi, M.P. 1983. Optimization by simulated annealing. Science 220(4598): 671-678.

Kuh, E.S., Kashiwabara, T. & Fujisawa, T. 1979. On optimum single-row routing. IEEE Transactions Circuit and Systems 26(6): 361-368.

Loh, S.L., Salleh, S. & Sarmin, N.H. 2014. An extended partitioning technique to transform trees into single-row networks. Applied Soft Computing 22: 483-491.

Loh, S.L., Salleh, S. & Sarmin, N.H. 2012. Partitioning technique for transforming perfect binary trees into single-row networks. Japan Journal of Industrial and Applied Mathematics 29(2): 317-330.

Loh, S.L., Salleh, S. & Sarmin, N.H. 2011. Partitioning technique for transformation of connected graphs into single-row network. Jurnal Teknologi 55 (Sains & Kej.) Special Issue (1): 241-253.

Loh, S.L., Salleh, S. & Sarmin, N.H. 2010. Spanning tree transformation of connected graph into single-row network. In Proceedings of International Conference on Computational and Mathematical Engineering. Bayview Hotel Georgetown, Penang, Malaysia. 24 - 25 February. pp. 597-601.

Loh, S.L., Salleh, S. & Sarmin, N.H. 2008. Double simulated annealing model for mapping of graphs to single-row networks. In Advances in Fundamentals and Social Sciences. Johor: Penerbit Universiti Teknologi Malaysia. pp. 51-64.

Salleh, S., Olariu, S. & Sanugi, B. 2005. Single-row transformation of complete graphs. Journal of Supercomputing 31: 265-279.

Salleh, S., Olariu, S., Zomaya, A.Y., Kiew, L.Y. & Aziz, N.A.B. 2007. Single-row mapping and transformation of connected graphs. Journal of Supercomputing 39: 73-89.

Salleh, S., Sanugi, B., Jamaludin, H., Olariu, S. & Zomaya, A.Y. 2002. Enhanced simulated annealing technique for the single-row routing problem. Journal of Supercomputing 21(3): 285-302.

Tarng, T.T., Sadowska, M.M. & Kuh, E.S. 1984. An efficient single-row algorithm. IEEE Transactions on Computer-Aided Design 3(3): 178-183.

Ting, B.S., Kuh, E.S. & Shirakawa, L. 1976. The multilayer routing problem:  Algorithms and necessary and sufficient conditions for the single row, single layer case. IEEE Transactions Circuit and Systems 23:768-778.

*Pengarang untuk surat-menyurat; email: nhs@utm.my