Skip to main navigation Skip to search Skip to main content

Node-independent spanning trees in Gaussian networks

Research output: Contribution to journal › Article › peer-review

14 Scopus citations

Abstract

Message broadcasting in networks can be efficiently carried over spanning trees. A set of spanning trees in the same network is node independent if two conditions are satisfied. First, all trees are rooted at the same node r. Second, for every node u in the network, all trees’ paths from r to u are node-disjoint, excluding the end nodes r and u. Independent spanning trees have applications in fault-tolerant communications and secure message distributions. Gaussian networks and two-dimensional toroidal networks share similar topological characteristics. They are regular of degree four, symmetric, and node-transitive. Gaussian networks, however, have relatively lesser network diameter that could result in a better performance. This promotes Gaussian networks to be a potential alternative for two-dimensional toroidal networks. In this paper, we present constructions for node independent spanning trees in dense Gaussian networks. Based on these constructions, we design routing algorithms that can be used in fault-tolerant routing and secure message distribution. We also design fault-tolerant algorithms to construct these trees in parallel.

Original languageEnglish
Pages (from-to)324-332
Number of pages9
JournalJournal of Parallel and Distributed Computing
Volume109
DOIs
StatePublished - Nov 2017

Keywords

  • Circulant graphs
  • Fault-tolerant routing
  • Gaussian networks
  • Independent spanning trees
  • Spanning trees

Fingerprint

Dive into the research topics of 'Node-independent spanning trees in Gaussian networks'. Together they form a unique fingerprint.

Cite this