Single-row mapping and transformation of connected graphs
In a dimensional problem, the transformation of a graph into its linear network can be viewed as a transition involving demand and supply. A connected graph represents the demand flows between the components in the graph while the network supporting it is the resource or capacity links for supportin...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Springer Netherlands
2007
|
| Online Access: | http://eprints.utm.my/7542/1/Salleh_Shaharuddin_2007_Single-Row_Mapping_Transformation_Connected_Graphs.pdf |
| _version_ | 1796854233398509568 |
|---|---|
| author | Salleh, Shaharuddin Hussain Olariu, Stephan Zomaya, Albert Y H Yieng, K.L B. Aziz, Nur Arina |
| author_facet | Salleh, Shaharuddin Hussain Olariu, Stephan Zomaya, Albert Y H Yieng, K.L B. Aziz, Nur Arina |
| author_sort | Salleh, Shaharuddin Hussain |
| collection | ePrints |
| description | In a dimensional problem, the transformation of a graph into its linear network can be viewed as a transition involving demand and supply. A connected graph represents the demand flows between the components in the graph while the network supporting it is the resource or capacity links for supporting the demand volumes. The transformation involves a mapping from the graph to its network to satisfy certain performance metrics. In this work, we propose a model for transforming a connected graph to its linear network model in the form of a single-row routing network. The main objective is to provide an optimum routing network that minimizes the congestion. In this technique, the given graph is first partitioned into several disjoint cliques using the Hopfield neural network using our model called AdCliq. From the cliques, a set of intervals derived from the zones are obtained through the matching nodes in the single-row axis. The intervals are then mapped into a network of non-crossing nets using our previously developed tool called ESSR. The network is optimal in terms of minimum street congestion and number of doglegs, and this provides a reasonably good step towards the overall solution to the demand-supply problem. |
| first_indexed | 2024-03-05T18:11:21Z |
| format | Article |
| id | utm.eprints-7542 |
| institution | Universiti Teknologi Malaysia - ePrints |
| language | English |
| last_indexed | 2024-03-05T18:11:21Z |
| publishDate | 2007 |
| publisher | Springer Netherlands |
| record_format | dspace |
| spelling | utm.eprints-75422017-10-23T03:56:35Z http://eprints.utm.my/7542/ Single-row mapping and transformation of connected graphs Salleh, Shaharuddin Hussain Olariu, Stephan Zomaya, Albert Y H Yieng, K.L B. Aziz, Nur Arina In a dimensional problem, the transformation of a graph into its linear network can be viewed as a transition involving demand and supply. A connected graph represents the demand flows between the components in the graph while the network supporting it is the resource or capacity links for supporting the demand volumes. The transformation involves a mapping from the graph to its network to satisfy certain performance metrics. In this work, we propose a model for transforming a connected graph to its linear network model in the form of a single-row routing network. The main objective is to provide an optimum routing network that minimizes the congestion. In this technique, the given graph is first partitioned into several disjoint cliques using the Hopfield neural network using our model called AdCliq. From the cliques, a set of intervals derived from the zones are obtained through the matching nodes in the single-row axis. The intervals are then mapped into a network of non-crossing nets using our previously developed tool called ESSR. The network is optimal in terms of minimum street congestion and number of doglegs, and this provides a reasonably good step towards the overall solution to the demand-supply problem. Springer Netherlands 2007-01 Article PeerReviewed application/pdf en http://eprints.utm.my/7542/1/Salleh_Shaharuddin_2007_Single-Row_Mapping_Transformation_Connected_Graphs.pdf Salleh, Shaharuddin Hussain and Olariu, Stephan and Zomaya, Albert Y H and Yieng, K.L and B. Aziz, Nur Arina (2007) Single-row mapping and transformation of connected graphs. Journal of Supercomputing, 30 (1). pp. 73-89. ISSN 1573-0484 http://dx.doi.org/10.1007/s11227-006-0005-4 10.1007/s11227-006-0005-4 |
| spellingShingle | Salleh, Shaharuddin Hussain Olariu, Stephan Zomaya, Albert Y H Yieng, K.L B. Aziz, Nur Arina Single-row mapping and transformation of connected graphs |
| title | Single-row mapping and transformation of connected graphs |
| title_full | Single-row mapping and transformation of connected graphs |
| title_fullStr | Single-row mapping and transformation of connected graphs |
| title_full_unstemmed | Single-row mapping and transformation of connected graphs |
| title_short | Single-row mapping and transformation of connected graphs |
| title_sort | single row mapping and transformation of connected graphs |
| url | http://eprints.utm.my/7542/1/Salleh_Shaharuddin_2007_Single-Row_Mapping_Transformation_Connected_Graphs.pdf |
| work_keys_str_mv | AT sallehshaharuddinhussain singlerowmappingandtransformationofconnectedgraphs AT olariustephan singlerowmappingandtransformationofconnectedgraphs AT zomayaalbertyh singlerowmappingandtransformationofconnectedgraphs AT yiengkl singlerowmappingandtransformationofconnectedgraphs AT baziznurarina singlerowmappingandtransformationofconnectedgraphs |