Constructing edge-disjoint spanning trees in locally twisted cubes

DOI10.1016/j.tcs.2008.12.025zbMath1162.68046OpenAlexW2054028559MaRDI QIDQ1006074

Sun-Yuan Hsieh, Chang-Jen Tu

Publication date: 17 March 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.12.025

zbMATH Keywords

edge-disjoint spanning treesgraph-theoretic interconnection networkslocally twisted cubesdesign and analysis of algorithmsdata broadcasting

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10)

Related Items (44)

Construction independent spanning trees on locally twisted cubes in parallel ⋮ Locally exchanged twisted cubes: connectivity and super connectivity ⋮ Paths and cycles identifying vertices in twisted cubes ⋮ Constructing edge-disjoint spanning trees in twisted cubes ⋮ Embedding mutually edge-disjoint cycles into locally twisted cubes ⋮ Edge-disjoint paths in faulty augmented cubes ⋮ Improving the panconnectedness property of locally twisted cubes ⋮ The \(g\)-good-neighbor diagnosability of locally twisted cubes ⋮ The crossing number of locally twisted cubes \(L T Q_n\) ⋮ An algorithm to construct independent spanning trees on parity cubes ⋮ Hamiltonian paths and cycles pass through prescribed edges in the balanced hypercubes ⋮ The generalized 4-connectivity of locally twisted cubes ⋮ Reliability evaluation for bijection-connected networks based on the super \(P_k\)-connectivity ⋮ Optimal broadcasting for locally twisted cubes ⋮ Parallel construction of optimal independent spanning trees on Cartesian product of complete graphs ⋮ Embedding three edge-disjoint Hamiltonian cycles into locally twisted cubes ⋮ Embedding two edge-disjoint Hamiltonian cycles into locally twisted cubes ⋮ Symmetric property and reliability of locally twisted cubes ⋮ Dimension-adjacent trees and parallel construction of independent spanning trees on crossed cubes ⋮ Independent spanning trees vs. edge-disjoint spanning trees in locally twisted cubes ⋮ Hamiltonian cycles and paths in faulty twisted hypercubes ⋮ The property of edge-disjoint Hamiltonian cycles in transposition networks and hypercube-like networks ⋮ Independent spanning trees on twisted cubes ⋮ Super fault-tolerance assessment of locally twisted cubes based on the structure connectivity ⋮ Flexible cycle embedding in the locally twisted cube with nodes positioned at any prescribed distance ⋮ Construction of optimal independent spanning trees on folded hypercubes ⋮ A parallel algorithm for constructing independent spanning trees in twisted cubes ⋮ Constructing completely independent spanning trees in crossed cubes ⋮ The generalized 4-connectivity of hypercubes ⋮ Edge-independent spanning trees in augmented cubes ⋮ Constructing independent spanning trees for locally twisted cubes ⋮ A novel algorithm to embed a multi-dimensional torus into a locally twisted cube ⋮ Linear layout of locally twisted cubes ⋮ Fault-tolerant edge-pancyclicity of locally twisted cubes ⋮ Embedding of tori and grids into twisted cubes ⋮ Broadcasting secure messages via optimal independent spanning trees in folded hypercubes ⋮ Independent spanning trees on folded hyper-stars ⋮ Independent spanning trees in crossed cubes ⋮ An improved algorithm to construct edge-independent spanning trees in augmented cubes ⋮ A two-stages tree-searching algorithm for finding three completely independent spanning trees ⋮ Constructing Node-Independent Spanning Trees in Augmented Cubes ⋮ Changing the diameter of the locally twisted cube ⋮ A parallel algorithm to construct edge independent spanning trees on the line graphs of conditional bijective connection networks ⋮ Independent spanning trees in crossed cubes

Cites Work

• Independent spanning trees of chordal rings
• The multi-tree approach to reliability in distributed networks
• Arrangement graphs: A class of generalized star graphs
• Independent trees in planar graphs
• Embedding \(k\)(\(n-k\)) edge-disjoint spanning trees in arrangement graphs.
• Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs
• Edge-disjoint spanning trees on the star network with applications to fault tolerance
• The locally twisted cubes
• Optimum broadcasting and personalized communication in hypercubes
• Finding Four Independent Trees

This page was built for publication: Constructing edge-disjoint spanning trees in locally twisted cubes