The multi-tree approach to reliability in distributed networks

DOI10.1016/0890-5401(88)90016-8zbMath0655.68029OpenAlexW2022175859MaRDI QIDQ1109560

Publication date: 1988

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(88)90016-8

zbMATH Keywords

reliability spanning tree distributed algorithms communication protocol network of asynchronous processors

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Reliability, availability, maintenance, inspection in operations research (90B25) Applications of graph theory to circuits and networks (94C15) Theory of operating systems (68N25) Algorithms in computer science (68W99)

Related Items (67)

Construction independent spanning trees on locally twisted cubes in parallel ⋮ Independent spanning trees of chordal rings ⋮ Directed \(s\)-\(t\) numberings, rubber bands, and testing digraph \(k\)-vertex connecitivity ⋮ Degree condition for completely independent spanning trees ⋮ Constructing edge-disjoint spanning trees in twisted cubes ⋮ A parallel algorithm for constructing multiple independent spanning trees in bubble-sort networks ⋮ Finding Totally Independent Spanning Trees with Linear Integer Programming ⋮ Unnamed Item ⋮ Biconnectivity, \(st\)-numbering and other applications of DFS using \(O(n)\) bits ⋮ An algorithm to construct independent spanning trees on parity cubes ⋮ Reliable broadcasting in product networks ⋮ Two completely independent spanning trees of claw-free graphs ⋮ A comment on ``Independent spanning trees in crossed cubes ⋮ A plane graph representation of triconnected graphs ⋮ Exact learning of multitrees and almost-trees using path queries ⋮ Output-sensitive reporting of disjoint paths (extended abstract) ⋮ Edge-independent spanning trees in folded crossed cubes ⋮ Parallel construction of optimal independent spanning trees on Cartesian product of complete graphs ⋮ Computing all the best swap edges distributively ⋮ Two completely independent spanning trees of \(P_4\)-free graphs ⋮ Dimension-adjacent trees and parallel construction of independent spanning trees on crossed cubes ⋮ Constructing dual-CISTs of folded divide-and-swap cubes ⋮ Independent spanning trees vs. edge-disjoint spanning trees in locally twisted cubes ⋮ Spanning trees: A survey ⋮ Independent spanning trees on twisted cubes ⋮ A fast parallel algorithm for constructing independent spanning trees on parity cubes ⋮ Optimal fault-tolerant routings for connected graphs ⋮ Forests, frames, and games: Algorithms for matroid sums and applications ⋮ Construction of optimal independent spanning trees on folded hypercubes ⋮ Edge-orders ⋮ A parallel algorithm for constructing independent spanning trees in twisted cubes ⋮ Constructing completely independent spanning trees in crossed cubes ⋮ On mixed connectivity certificates ⋮ Completely independent spanning trees in torus networks ⋮ Edge-independent spanning trees in augmented cubes ⋮ Parallel construction of multiple independent spanning trees on highly scalable datacenter networks ⋮ On independent spanning trees ⋮ Independent tree spanners: Fault-tolerant spanning trees with constant distance guarantees ⋮ Constructing independent spanning trees for locally twisted cubes ⋮ Rainbow vertex-connection and graph products ⋮ Independent spanning trees on even networks ⋮ Independent spanning trees with small depths in iterated line digraphs ⋮ Disjoint paths in arborescences ⋮ Structural properties of subdivided-line graphs ⋮ CONSTRUCTING MULTIPLE INDEPENDENT SPANNING TREES ON RECURSIVE CIRCULANT GRAPHS G(2^m, 2) ⋮ Broadcasting secure messages via optimal independent spanning trees in folded hypercubes ⋮ Constructing Internally Disjoint Pendant Steiner Trees in Cartesian Product Networks ⋮ The <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>k</mml:mi></mml:math>-independence number of graph products ⋮ Independent spanning trees on folded hyper-stars ⋮ Monochromatic connectivity and graph products ⋮ Constructing edge-disjoint spanning trees in locally twisted cubes ⋮ On the independent spanning trees of recursive circulant graphs \(G(cd^m,d)\) with \(d>2\) ⋮ An improved algorithm to construct edge-independent spanning trees in augmented cubes ⋮ On mixed connectivity certificates ⋮ Mondshein Sequences (a.k.a. (2,1)-Orders) ⋮ Constructing Node-Independent Spanning Trees in Augmented Cubes ⋮ Spanning tree packing number and eigenvalues of graphs with given girth ⋮ A multi-tree routing scheme using acyclic orientations ⋮ Random sampling and greedy sparsification for matroid optimization problems ⋮ Amortized efficiency of constructing multiple independent spanning trees on bubble-sort networks ⋮ Degree conditions for completely independent spanning trees of bipartite graphs ⋮ Four Edge-Independent Spanning Trees ⋮ On the complexity of computation in the presence of link failures: The case of a ring ⋮ A parallel algorithm to construct edge independent spanning trees on the line graphs of conditional bijective connection networks ⋮ Independent spanning trees in crossed cubes ⋮ Independent trees in graphs ⋮ Electing a leader in a ring with link failures

Cites Work

This page was built for publication: The multi-tree approach to reliability in distributed networks