One-to-One Disjoint Path Covers on WK-Networks

Lan Tao You; Yue Juan Han

doi:10.4028/www.scientific.net/AMM.651-653.1875

Paper Titles

Implementation and Application of an Algorithm for System Menu Traversal in C#
p.1856

Implementation of Monitoring and Management for Professional Mobile Application Adapting to Scenarios Switch
p.1860

Massive Data Hybrid Encryption Algorithm Based on Cloud Computing
p.1864

Network Routing Mechanism Simulation Research Based on VANETs
p.1868

One-to-One Disjoint Path Covers on WK-Networks
p.1875

Optimization of the Virtual Potential Field Based on Coverage-Enhancing Algorithm for Directional Sensor Networks
p.1882

Real-Time Embedded Software Architecture Modeling and Reliability Evaluation Based on Time-Extended Petri Net
p.1888

Research and Design of Enterprise-Class Network Data Center Based on Cloud Computing
p.1893

Research and Implementation of Topic Crawler Based on Hadoop
p.1896

HomeApplied Mechanics and MaterialsApplied Mechanics and Materials Vols. 651-653One-to-One Disjoint Path Covers on WK-Networks

One-to-One Disjoint Path Covers on WK-Networks

Abstract:

The WK-recursive network has received much attention due to its many attractive properties. In this paper, we consider the one-to-one disjoint path covers properties of the WK-recursive network. We use K(d, t) to denote the WK-recursive network of level t, each of which basic modules is a d-vertex complete graph, where d > 1 and t ≥ 1. We prove that for any two distinct vertices u and v, there exist d-1 node-disjoint paths whose union covers all vertices of K(d, t) for d ≥ 3 and t ≥ 1. The results is optimal for vertices in different K_j₍d, t − 1) for t ≥ 2, since each K_j(d, t − 1) with 1 ≤ j ≤ d has d − 1 open edges.

You might also be interested in these eBooks

Material Science, Civil Engineering and Architecture Science, Mechanical Engineering and Manufacturing Technology II

View Preview

Info:

Periodical:

Applied Mechanics and Materials (Volumes 651-653)

Pages:

1875-1881

DOI:

https://doi.org/10.4028/www.scientific.net/AMM.651-653.1875

Citation:

Cite this paper

Online since:

September 2014

Authors:

Lan Tao You*, Yue Juan Han

Keywords:

Disjoint Path Cover, Hamiltonian, Interconnection Network, WK-Recursive Network

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

* - Corresponding Author

References

[1] P. -L. Lai, H. -C. Hsu, On the two-equal-disjoint path cover problem of crossed cubes, Proc. Ninth Joint Int'l Conf. Information Sciences (JCIS '06) (2006) 603–606.

DOI: 10.2991/jcis.2006.204

Google Scholar

[2] K. Day, A.E. Al-Ayyoub, Fault diameter of k-ary n-cube networks, IEEE Transactions on Parallel and Distributed Systems 8 (1997) 903–907.

DOI: 10.1109/71.615436

Google Scholar

[3] Y. -K. Shih, S. -S. Kao, One-to-one disjoint path covers on k-ary n-cubes, Theoretical Computer Science 412 (35) (2011) 4513–4530.

DOI: 10.1016/j.tcs.2011.04.035

Google Scholar

[4] G. Della Vecchia, C. Sanges, Recursively scalable networks for message passing architectures, in: E. Chiricozzi, A. D'Amico (Eds. ), Parallel Processing and Applications, Elsevier North-Holland, Amsterdam, 1988, 33–40.

Google Scholar

[5] J.S. Fu, Hamiltonicity of the WK-recursive network with and without faulty nodes, IEEE Trans. Paral. Distrib. Syst. 16 (2005) 853–865.

DOI: 10.1109/tpds.2005.109

Google Scholar

[6] J.S. Fu, Hamiltonian connectivity of the WK-recursive network with faulty nodes, Information Sciences 178 (2008) 2573–2584.

DOI: 10.1016/j.ins.2008.02.011

Google Scholar

[7] T. -Y. Ho, C. -K. Lin, J.J.M. Tan, L. -H. Hsu, Fault-tolerant hamiltonian connectivity of the WKrecursive networks, Information Sciences 271 (2014) 236–245.

DOI: 10.1016/j.ins.2014.02.087

Google Scholar

[8] S. Bakhshi, H. Sarbazi-Azad, One-to-one and One-to-many node-disjoint Routing Algorithms for WKRecursive networks, The International Symposium on Parallel Architectures, Algorithms, and Networks 54 (2008) 227–232.

DOI: 10.1109/i-span.2008.37

Google Scholar