An Optimal Synchronizer for the Hypercube
From MaRDI portal
Publication:4730798
DOI10.1137/0218050zbMath0681.68091OpenAlexW2018963243MaRDI QIDQ4730798
Jeffrey D. Ullman, David Peleg
Publication date: 1989
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0218050
Related Items
On approximating tree spanners that are breadth first search trees, Tentative and definite distributed computations: An optimistic approach to network synchronization, Spanners of de Bruijn and Kautz graphs, Euclidean Steiner Spanners: Light and Sparse, Graph spanners in the streaming model: An experimental study, Tree-decompositions with bags of small diameter, Methods and problems of communication in usual networks, Small stretch \((\alpha ,\beta )\)-spanners in the streaming model, Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models, Small Stretch Pairwise Spanners and Approximate $D$-Preservers, Generating sparse spanners for weighted graphs, Generating sparse 2—spanners, Collective tree spanners in graphs with bounded parameters, Additive Spanners for Circle Graphs and Polygonal Graphs, Spanners for bounded tree-length graphs, Balancing minimum spanning trees and shortest-path trees, Isomorphic tree spanner problems, Minimum \(t\)-spanners on subcubic graphs, The use of a synchronizer yields the maximum computation rate in distributed networks, Parameterized complexity of directed spanner problems, Restrictions of minimum spanner problems, Can we locally compute sparse connected subgraphs?, Optimality computation of the minimum stretch spanning tree problem, Degree-constrained spanners for multidimensional grids, A PTAS for the sparsest 2-spanner of 4-connected planar triangulations, Chasing a Fast Robber on Planar Graphs and Random Graphs, Tree 3-spanners in 2-sep chordal graphs: characterization and algorithms, General variable neighborhood search for the minimum stretch spanning tree problem, Demand-aware network designs of bounded degree, Distributed distance computation and routing with small messages, Tree 3-spanners on generalized prisms of graphs, Improved NP-hardness results for the minimum \(t\)-spanner problem on bounded-degree graphs, Tree spanners of bounded degree graphs, New pairwise spanners, Approximation of minimum weight spanners for sparse graphs, Sparse reliable graph backbones, Spanners of bounded degree graphs, Rumor Spreading with No Dependence on Conductance, Online Spanners in Metric Spaces, The sparsest additive spanner via multiple weighted BFS trees, Unnamed Item, Collective additive tree spanners for circle graphs and polygonal graphs, A parallel bio-inspired shortest path algorithm, Spanners and message distribution in networks., Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs, Spanners in sparse graphs, Fast deterministic distributed algorithms for sparse spanners, Simple Distributed Spanners in Dense Congest Networks, Hardness and efficiency on \(t\)-admissibility for graph operations, Tree 3-spanners on interval, permutation and regular bipartite graphs, Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model, Improved Approximation for the Directed Spanner Problem, On sparse spanners of weighted graphs, Combinatorial network abstraction by trees and distances, Parameterized Complexity of Directed Spanner Problems., A linear time algorithm to construct a tree 4-spanner on trapezoid graphs, A simple and efficient kinetic spanner, Multipath Spanners via Fault-Tolerant Spanners, Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences, Bypassing Erdős’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners, \(f\)-sensitivity distance oracles and routing schemes, Tree spanners in planar graphs, Independent tree spanners: Fault-tolerant spanning trees with constant distance guarantees, Max-stretch reduction for tree spanners, Edge-disjoint spanners in Cartesian products of graphs, An approximation algorithm for the edge-dilation \(k\)-center problem., Approximating \(k\)-spanner problems for \(k>2\), Transitive-Closure Spanners: A Survey, A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs, Distributed construction of purely additive spanners, Unnamed Item, Unnamed Item, Graph spanners: a tutorial review, Minimax flow tree problems, Connections between Theta-Graphs, Delaunay Triangulations, and Orthogonal Surfaces, NP-hardness and fixed-parameter tractability of the minimum spanner problem, Refined Vertex Sparsifiers of Planar Graphs, The Greedy Spanner Is Existentially Optimal, Message lower bounds via efficient network synchronization, On the memory overhead of distributed snapshots, The minimum stretch spanning tree problem for typical graphs, On 2-detour subgraphs of the hypercube, Edge tree spanners, The Sparsest Additive Spanner via Multiple Weighted BFS Trees, Edge-disjoint spanners in tori, Congested Clique Algorithms for Graph Spanners, Additive tree 2-spanners of permutation graphs, Message Lower Bounds via Efficient Network Synchronization, The non-approximability of bicriteria network design problems, Sparse hypercube 3-spanners, Distributed Spanner Approximation, Self-spanner graphs, Mixed-integer programming approaches for the tree \(t^*\)-spanner problem, Light spanners for high dimensional norms via stochastic decompositions, Edge-disjoint spanners of complete graphs and complete digraphs, Additive sparse spanners for graphs with bounded length of largest induced cycle, Fault tolerant additive and \((\mu, \alpha)\)-spanners, Local majorities, coalitions and monopolies in graphs: A review, Lasserre integrality gaps for graph spanners and related problems
