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

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...

Full description

Bibliographic Details
Main Authors:	Ser, Lee Loh, Shaharuddin Salleh, Nor Haniza Sarmin
Format:	Article
Language:	English
Published:	Universiti Kebangsaan Malaysia 2014
Online Access:	http://journalarticle.ukm.my/7525/ http://journalarticle.ukm.my/7525/ http://journalarticle.ukm.my/7525/1/19_Ser_Lee_Loh.pdf

id	ukm-7525
recordtype	eprints
spelling	ukm-75252016-12-14T06:44:22Z http://journalarticle.ukm.my/7525/ Linear-time heuristic partitioning technique for mapping of connected graphs into single-row networks Ser, Lee Loh Shaharuddin Salleh, Nor Haniza Sarmin, 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. Universiti Kebangsaan Malaysia 2014-08 Article PeerReviewed application/pdf en http://journalarticle.ukm.my/7525/1/19_Ser_Lee_Loh.pdf Ser, Lee Loh and Shaharuddin Salleh, and Nor Haniza Sarmin, (2014) Linear-time heuristic partitioning technique for mapping of connected graphs into single-row networks. Sains Malaysiana, 43 (8). pp. 1263-1269. ISSN 0126-6039 http://www.ukm.my/jsm
repository_type	Digital Repository
institution_category	Local University
institution	Universiti Kebangasaan Malaysia
building	UKM Institutional Repository
collection	Online Access
language	English
description	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.
format	Article
author	Ser, Lee Loh Shaharuddin Salleh, Nor Haniza Sarmin,
spellingShingle	Ser, Lee Loh Shaharuddin Salleh, Nor Haniza Sarmin, Linear-time heuristic partitioning technique for mapping of connected graphs into single-row networks
author_facet	Ser, Lee Loh Shaharuddin Salleh, Nor Haniza Sarmin,
author_sort	Ser, Lee Loh
title	Linear-time heuristic partitioning technique for mapping of connected graphs into single-row networks
title_short	Linear-time heuristic partitioning technique for mapping of connected graphs into single-row networks
title_full	Linear-time heuristic partitioning technique for mapping of connected graphs into single-row networks
title_fullStr	Linear-time heuristic partitioning technique for mapping of connected graphs into single-row networks
title_full_unstemmed	Linear-time heuristic partitioning technique for mapping of connected graphs into single-row networks
title_sort	linear-time heuristic partitioning technique for mapping of connected graphs into single-row networks
publisher	Universiti Kebangsaan Malaysia
publishDate	2014
url	http://journalarticle.ukm.my/7525/ http://journalarticle.ukm.my/7525/ http://journalarticle.ukm.my/7525/1/19_Ser_Lee_Loh.pdf
first_indexed	2023-09-18T19:49:57Z
last_indexed	2023-09-18T19:49:57Z
_version_	1777406152603074560

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

Similar Items