Sublinear fully distributed partition with applications
From MaRDI portal
Publication:1959378
DOI10.1007/s00224-009-9190-xzbMath1206.68358OpenAlexW2135007303MaRDI QIDQ1959378
Akka Zemmari, Bilel Derbel, Mohamed Mosbah
Publication date: 6 October 2010
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-009-9190-x
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Distributed algorithms (68W15)
Related Items (10)
Derandomizing local distributed algorithms under bandwidth restrictions ⋮ Rumor Spreading with No Dependence on Conductance ⋮ Sublinear fully distributed partition with applications ⋮ Making Asynchronous Distributed Computations Robust to Channel Noise ⋮ Simple Distributed Spanners in Dense Congest Networks ⋮ Making asynchronous distributed computations robust to noise ⋮ About randomised distributed graph colouring and graph partition algorithms ⋮ Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set ⋮ Congested Clique Algorithms for Graph Spanners ⋮ Distributed Spanner Approximation
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Deterministic small-world communication networks
- Fast distributed network decompositions and covers
- Self-stabilizing deterministic network decomposition
- On sparse spanners of weighted graphs
- Simple and efficient network decomposition and synchronization
- Randomized local elections.
- Characterizations of classes of graphs recognizable by local computations
- Sublinear fully distributed partition with applications
- A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction
- On the locality of distributed sparse spanner construction
- Spanners and emulators with sublinear distance errors
- Complexity of network synchronization
- Locality in Distributed Graph Algorithms
- Routing with Polynomial Communication-Space Trade-Off
- Sparser: A Paradigm for Running Distributed Algorithms
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Near-Linear Time Construction of Sparse Neighborhood Covers
- Fast Distributed Construction of Smallk-Dominating Sets and Applications
- Different local controls for graph relabeling systems
- Online tracking of mobile users
- A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
- Centralized broadcast in multihop radio networks
- Distributed Computing: A Locality-Sensitive Approach
- $(1 + \epsilon,\beta)$-Spanner Constructions for General Graphs
- Low Distortion Spanners
- Mathematical Foundations of Computer Science 2005
- Efficient algorithms for constructing (1+,ε, β)-spanners in the distributed and streaming models
- Automata, Languages and Programming
- Computing almost shortest paths
- Distributed algorithms for ultrasparse spanners and linear size skeletons
This page was built for publication: Sublinear fully distributed partition with applications
