Spanning Tree Transformation of Connected Graphs into Single-Row Networks

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

Authors:

• S.L. Loh
• S. Salleh
• N.H. Sarmin

Keywords:

• Graph theory
• simulated annealing
• single-rowrouting and spanning tree.

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.