On Directed Edge-Disjoint Spanning Trees in Product Networks, An Algorithmic Approach
In (Ku et al. 2003), the authors have proposed a construction of edge-disjoint spanning trees EDSTs in undirected product networks. Their construction method focuses more on showing the existence of a maximum number (n1+n2-1) of EDSTs in product network of two graphs, where factor graphs have respec...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Sultan Qaboos University
2014-12-01
|
| Series: | The Journal of Engineering Research |
| Subjects: | |
| Online Access: | https://journals.squ.edu.om/index.php/tjer/article/view/149 |
| _version_ | 1828776982173712384 |
|---|---|
| author | A.R. Touzene K. Day |
| author_facet | A.R. Touzene K. Day |
| author_sort | A.R. Touzene |
| collection | DOAJ |
| description | In (Ku et al. 2003), the authors have proposed a construction of edge-disjoint spanning trees EDSTs in undirected product networks. Their construction method focuses more on showing the existence of a maximum number (n1+n2-1) of EDSTs in product network of two graphs, where factor graphs have respectively n1 and n2 EDSTs. In this paper, we propose a new systematic and algorithmic approach to construct (n1+n2) directed routed EDST in the product networks. The direction of an edge is added to support bidirectional links in interconnection networks. Our EDSTs can be used straightforward to develop efficient collective communication algorithms for both models store-and-forward and wormhole. |
| first_indexed | 2024-12-11T16:11:00Z |
| format | Article |
| id | doaj.art-4615294ab28d41e18a49d0b3cbbdaef9 |
| institution | Directory Open Access Journal |
| issn | 1726-6009 1726-6742 |
| language | English |
| last_indexed | 2024-12-11T16:11:00Z |
| publishDate | 2014-12-01 |
| publisher | Sultan Qaboos University |
| record_format | Article |
| series | The Journal of Engineering Research |
| spelling | doaj.art-4615294ab28d41e18a49d0b3cbbdaef92022-12-22T00:59:04ZengSultan Qaboos UniversityThe Journal of Engineering Research1726-60091726-67422014-12-01112798810.24200/tjer.vol11iss2pp79-88149On Directed Edge-Disjoint Spanning Trees in Product Networks, An Algorithmic ApproachA.R. Touzene0K. Day1Department of Computer Science, College of Science, Sultan Qaboos University, P.O. Box 36, Postal Code 123, Al-Khodh, Muscat, Sultanate of Oman.Department of Computer Science, College of Science, Sultan Qaboos University, P.O. Box 36, Postal Code 123, Al-Khodh, Muscat, Sultanate of Oman.In (Ku et al. 2003), the authors have proposed a construction of edge-disjoint spanning trees EDSTs in undirected product networks. Their construction method focuses more on showing the existence of a maximum number (n1+n2-1) of EDSTs in product network of two graphs, where factor graphs have respectively n1 and n2 EDSTs. In this paper, we propose a new systematic and algorithmic approach to construct (n1+n2) directed routed EDST in the product networks. The direction of an edge is added to support bidirectional links in interconnection networks. Our EDSTs can be used straightforward to develop efficient collective communication algorithms for both models store-and-forward and wormhole.https://journals.squ.edu.om/index.php/tjer/article/view/149product networks, directed edge-disjoint spanning trees, interconnection networks. |
| spellingShingle | A.R. Touzene K. Day On Directed Edge-Disjoint Spanning Trees in Product Networks, An Algorithmic Approach The Journal of Engineering Research product networks, directed edge-disjoint spanning trees, interconnection networks. |
| title | On Directed Edge-Disjoint Spanning Trees in Product Networks, An Algorithmic Approach |
| title_full | On Directed Edge-Disjoint Spanning Trees in Product Networks, An Algorithmic Approach |
| title_fullStr | On Directed Edge-Disjoint Spanning Trees in Product Networks, An Algorithmic Approach |
| title_full_unstemmed | On Directed Edge-Disjoint Spanning Trees in Product Networks, An Algorithmic Approach |
| title_short | On Directed Edge-Disjoint Spanning Trees in Product Networks, An Algorithmic Approach |
| title_sort | on directed edge disjoint spanning trees in product networks an algorithmic approach |
| topic | product networks, directed edge-disjoint spanning trees, interconnection networks. |
| url | https://journals.squ.edu.om/index.php/tjer/article/view/149 |
| work_keys_str_mv | AT artouzene ondirectededgedisjointspanningtreesinproductnetworksanalgorithmicapproach AT kday ondirectededgedisjointspanningtreesinproductnetworksanalgorithmicapproach |