Routing with Polynomial Communication-Space Trade-Off
From MaRDI portal
Publication:4012441
DOI10.1137/0405013zbMath0762.68025OpenAlexW2005580106MaRDI QIDQ4012441
Publication date: 27 September 1992
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0405013
Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)
Related Items
Efficient algorithms for constructing \((1+\epsilon,\beta)\)-spanners in the distributed and streaming models, Small Stretch Pairwise Spanners and Approximate $D$-Preservers, A faster distributed protocol for constructing a minimum spanning tree, A complete characterization of the path layout construction problem for ATM networks with given hop count and load, Average stretch analysis of compact routing schemes, Prioritized Metric Structures and Embedding, Strong-diameter decompositions of minor free graphs, Distributed strong diameter network decomposition, Optimal layouts on a chain ATM network, Distributed distance computation and routing with small messages, New pairwise spanners, On multi-label linear interval routing schemes, Approximation of minimum weight spanners for sparse graphs, Sublinear fully distributed partition with applications, Universal routing schemes, Sparse communication networks and efficient routing in the plane, Compact and localized distributed data structures, On sparse spanners of weighted graphs, Compact roundtrip routing with topology-independent node names, Space-efficient path-reporting approximate distance oracles, Optimal layouts on a chain ATM network, Interval routing schemes, A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs, Unnamed Item, Deterministic M2M multicast in radio networks, Close to linear space routing schemes, Simple and efficient network decomposition and synchronization, Distributed Spanner Approximation, Graph theoretical issues in computer networks
