MODELS DEVELOPMENT FOR SINGLE–ROW NETWORKS FROM CONNECTED GRAPHS
DOI:
https://doi.org/10.11113/jt.v57.1529Keywords:
Single–row network, transformation, connected graph, tree, simulated annealingAbstract
In this paper, we present a collection of models for connected graphs mapping into single–row networks. The collection involves three specific models for perfect binary trees, trees and partially dense graphs, and three general models for connected graphs. These models are compared in terms of their structures, energy values, congestion and number of doglegs in the single–row transformation. The numerical experiments are run by each respective developed program. 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.References
B. S. Ting, E. S. Kuh, L. Shirakawa. 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.
E. S. Kuh, T. Kashiwabara, and T. Fujisawa. 1979. On Optimum Single-row Routing. IEEE Transactions Circuit and Systems. 26(6): 361-368.
T. T. Tarng, M. M. Sadowska, and E. S. Kuh. 1984. An Efficient Single-row Algorithm. IEEE Transactions on Computer-Aided Design. 3(3):1 78-183.
B. B. Bhattacharya, J. S. Deogun, and N. A. Sherwani. 1988. A Graph Theoretic Approach to Single Row Routing Problems. Proceedings of the 1988 IEEE International Symposium on Circuit and Systems. June 7-9, 1988. 2: 1437-1440.
S. Salleh, B. Sanugi, H. Jamaludin, S. Olariu, and A. Y. Zomaya. 2002. Enhanced Simulated Annealing Technique for the Single-Row Routing Problem. Journal of Supercomputing. 21(3): 285-302.
S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. 1983. Optimization by Simulated Annealing. Science. 220(4598): 671-678.
S. Salleh, S. Olariu and B. Sanugi. 2005. Single-row Transformation of Complete Graphs. Journal of Supercomputing. 31: 265-279.
S. Salleh, S. Olariu, A. Y. Zomaya, L.Y. Kiew and N.A.B. Aziz. 2007. Single-row Mapping and Transformation of Connected Graphs. Journal of Supercomputing. 39: 73-89.
S. L. Loh, S. Salleh and N. H. Sarmin. 2009. Mapping of Complete Binary Trees into Single-Row Networks. Proceedings of 5th Asian Mathematical Conference. Putra World Trade Center, Kuala Lumpur.
S. L. Loh, S. Salleh and N. H. Sarmin. 2009. Single-Row Transformation of Trees into Single-Row Networks. Prosiding Simposium Kebangsaan Sains Matematik ke-17. Mahkota Hotel, Melaka.
S. L. Loh, S. Salleh and N. H. Sarmin. 2010. Partitioning Technique for Transformation of Connected Graphs into Single-Row Networks. Proceedings of 3rd International Postgraduate Conference on Engineering Science and Humanities 2010. Universiti Teknologi Malaysia, Johor Bahru.
S. L. Loh, S. Salleh and N. H. Sarmin. 2008. Double Simulated Annealing Model for Mapping of Graphs to Single-Row Networks in Advances in Fundamentals and Social Sciences. Malaysia: Penerbit Universiti Teknologi Malaysia. 51-64. (ISBN 978-983-52-0608-5).
S. L. Loh, S. Salleh and N. H. Sarmin. 2009. Spanning Tree Transformation of Connected Graphs into Single-Row Networks. World Academy of Science, Engineering and Technology. 62: 597-601.
S. L. Loh, S. Salleh and N. H. Sarmin. 2011. Graph Partitioning Technique for Single-Row Transformation of a Connected Graph. Prosiding Simposium Kebangsaan Sains Matematik-19. Universiti Teknologi Mara, Penang.
Fiduccia, C. M. and Mattheyses, R. M. 1982. A Linear-time Heuristic for Improving Network Partitions. In Proc. 19th ACM/IEEE Design Automation Conference. 175-181.
Downloads
Published
Issue
Section
License
Copyright of articles that appear in Jurnal Teknologi belongs exclusively to Penerbit Universiti Teknologi Malaysia (Penerbit UTM Press). This copyright covers the rights to reproduce the article, including reprints, electronic reproductions, or any other reproductions of similar nature.
