The multi-tree approach to reliability in distributed networks
From MaRDI portal
Publication:1109560
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
reliabilityspanning treedistributed algorithmscommunication protocolnetwork of asynchronous processors
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)
Cites Work
Related Items (73)
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 ⋮ Detection Performance of the Majority Dominance Rule in $m$ -Ary Relay Trees With Node and Link Failures ⋮ 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 ⋮ Strongly proper connected coloring of graphs ⋮ 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(2m, 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 ⋮ Independent spanning trees of product graphs ⋮ \((t, s)\)-completely independent spanning trees ⋮ Constructing edge-disjoint spanning trees in locally twisted cubes ⋮ Every 2-connected \(\{\text{claw}, Z_2\}\)-free graph with minimum degree at least 4 contains two CISTs ⋮ Vertex-independent spanning trees in complete Josephus 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
This page was built for publication: The multi-tree approach to reliability in distributed networks
