NDLI: Parallel construction of independent spanning trees and an application in diagnosis on Möbius cubes

Content Provider	Springer Nature Link
Author	Cheng, Baolei Fan, Jianxi Jia, Xiaohua Jia, Juncheng
Copyright Year	2013
Abstract	Independent spanning trees (ISTs) on networks have applications to increase fault-tolerance, bandwidth, and security. Möbius cubes are a class of the important variants of hypercubes. A recursive algorithm to construct n ISTs on n-dimensional Möbius cube M $_{ n }$ was proposed in the literature. However, there exists dependency relationship during the construction of ISTs and the time complexity of the algorithm is as high as O(NlogN), where N=2$^{ n }$ is the number of vertices in M $_{ n }$ and n≥2. In this paper, we study the parallel construction and a diagnostic application of ISTs on Möbius cubes. First, based on a circular permutation n−1,n−2,…,0 and the definitions of dimension-backbone walk and dimension-backbone tree, we propose an O(N) parallel algorithm, called PMCIST, to construct n ISTs rooted at an arbitrary vertex on M $_{ n }$. Based on algorithm PMCIST, we further present an O(n) parallel algorithm. Then we provide a parallel diagnostic algorithm with high efficiency to diagnose all the vertices in M $_{ n }$ by at most n+1 steps, provided the number of faulty vertices does not exceed n. Finally, we present simulation experiments of ISTs and an application of ISTs in diagnosis on 0-M $_{4}$.
Starting Page	1279
Ending Page	1301
Page Count	23
File Format	PDF
ISSN	09208542
Journal	The Journal of Supercomputing
Volume Number	65
Issue Number	3
e-ISSN	15730484
Language	English
Publisher	Springer US
Publisher Date	2013-01-30
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Möbius cube Independent spanning tree Parallel algorithm Nonnegative vector Diagnosis Circular permutation Programming Languages, Compilers, Interpreters Processor Architectures Computer Science
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Information Systems Hardware and Architecture Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A fully parallelized scheme of constructing independent spanning trees on Möbius cubes

Optimal Independent Spanning Trees on Odd Graphs

Embedding complete binary trees into parity cubes

Mutually independent Hamiltonian cycles in dual-cubes

Edge-disjoint node-independent spanning trees in dense Gaussian networks

Degree constrained minimum spanning tree problem: a learning automata approach

The number of DFAs for a given spanning tree

Efficient Collective Communications in Dual-Cube

On Data Distributions in the Construction of Parallel Programs

Parallel construction of independent spanning trees and an application in diagnosis on Möbius cubes

Similar Documents

A fully parallelized scheme of constructing independent spanning trees on Möbius cubes

Optimal Independent Spanning Trees on Odd Graphs

Embedding complete binary trees into parity cubes

Mutually independent Hamiltonian cycles in dual-cubes

Edge-disjoint node-independent spanning trees in dense Gaussian networks

Degree constrained minimum spanning tree problem: a learning automata approach

The number of DFAs for a given spanning tree

Efficient Collective Communications in Dual-Cube

On Data Distributions in the Construction of Parallel Programs

Parallel construction of independent spanning trees and an application in diagnosis on Möbius cubes