Spanning Tree Transformation of Connected Graphs into Single-Row Networks

Authors: S.L. Loh, S. Salleh, N.H. Sarmin

Abstract:

A spanning tree of a connected graph is a tree which consists the set of vertices and some or perhaps all of the edges from the connected graph. In this paper, a model for spanning tree transformation of connected graphs into single-row networks, namely Spanning Tree of Connected Graph Modeling (STCGM) will be introduced. Path-Growing Tree-Forming algorithm applied with Vertex-Prioritized is contained in the model to produce the spanning tree from the connected graph. Paths are produced by Path-Growing and they are combined into a spanning tree by Tree-Forming. The spanning tree that is produced from the connected graph is then transformed into single-row network using Tree Sequence Modeling (TSM). Finally, the single-row routing problem is solved using a method called Enhanced Simulated Annealing for Single-Row Routing (ESSR).

Keywords: Graph theory, simulated annealing, single-rowrouting and spanning tree.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1332106

References:

[1] B. S. Ting, E. S. Kuh, L. Shirakawa. "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, 1976.
[2] E. S. Kuh, T. Kashiwabara, and T. Fujisawa, "On optimum single-row routing," IEEE Transactions Circuit and Systems, 26(6):361-368, 1979.
[3] T. T. Tarng, M. M. Sadowska, and E. S. Kuh. "An efficient single-row algorithm," IEEE Transactions on Computer-Aided Design, 3(3):178- 183, 1984.
[4] B. B. Bhattacharya, J. S. Deogun, and N. A. Sherwani. "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, 1988
[5] S. Salleh, B. Sanugi, H. Jamaludin, S. Olariu, and A. Y. Zomaya. "Enhanced simulated annealing technique for the single-row routing problem," Journal of Supercomputing, 21(3):285-302, 2002.
[6] S. Salleh, S. Olariu and B. Sanugi. "Single-row transformation of complete graphs," Journal of Supercomputing, 31, 265-279, 2005.
[7] S. Salleh, S. Olariu, A. Y. Zomaya, L.Y. Kiew and N.A.B. Aziz. "Single-row mapping and transformation of connected graphs," Journal of Supercomputing, 39:73-89, 2007.
[8] S. L. Loh, S. Salleh and N. H. Sarmin, "Double simulated annealing model for mapping of graphs to single-row networks," unpublished.
[9] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, "Optimization by simulated annealing." Science, 220(4598):671-678,1983.
[10] S. L. Loh, S. Salleh and N. H. Sarmin, "Mapping of complete binary tree into single-row network," Proceedings of the 2009 5th Asian Mathematical Conference. June 22-26, 2009.
[11] S. L. Loh, S. Salleh and N. H. Sarmin, "Single-row transformation of trees into single-row network," unpublished.