Fast Distributed Construction of Smallk-Dominating Sets and Applications
From MaRDI portal
Publication:4216145
DOI10.1006/jagm.1998.0929zbMath0919.68052OpenAlexW1534484868MaRDI QIDQ4216145
Publication date: 1998
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jagm.1998.0929
Related Items (36)
Latency, capacity, and distributed minimum spanning trees ⋮ A silent self-stabilizing algorithm for the generalized minimal \(k\)-dominating set problem ⋮ New bounds for multi-label interval routing ⋮ TIME OPTIMAL ALGORITHMS FOR BLACK HOLE SEARCH IN RINGS ⋮ A faster distributed protocol for constructing a minimum spanning tree ⋮ Unnamed Item ⋮ Tight bounds for distributed minimum-weight spanning tree verification ⋮ Distributed approximation of capacitated dominating sets ⋮ Node and edge averaged complexities of local graph problems ⋮ Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions ⋮ A distributed algorithm for directed minimum-weight spanning tree ⋮ The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs ⋮ An efficient algorithm for constructing a connected dominating set in mobile ad hoc networks ⋮ Distributed verification of minimum spanning trees ⋮ A fast distributed approximation algorithm for minimum spanning trees ⋮ Constructing near spanning trees with few local inspections ⋮ Sublinear fully distributed partition with applications ⋮ Local Maps: New Insights into Mobile Agent Algorithms ⋮ An efficient distributed algorithm for constructing small dominating sets ⋮ Fast deterministic distributed algorithms for sparse spanners ⋮ On efficient distributed construction of near optimal routing schemes ⋮ Low-congestion shortcut and graph parameters ⋮ Algebraic methods in the congested clique ⋮ On the Microscopic View of Time and Messages ⋮ Deterministic distributed construction of \(T\)-dominating sets in time \(T\) ⋮ Efficient distributed approximation algorithms via probabilistic tree embeddings ⋮ Constant-time distributed dominating set approximation ⋮ An efficient distributed algorithm for canonical labeling on directed split-stars ⋮ Local algorithms for sparse spanning graphs ⋮ Distributed MST for constant diameter graphs ⋮ Labeling schemes for tree representation ⋮ Sparsifying Congested Cliques and Core-Periphery Networks ⋮ A distributed algorithm to find \(k\)-dominating sets ⋮ A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths ⋮ Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time ⋮ Approximate minimum directed spanning trees under congestion
This page was built for publication: Fast Distributed Construction of Smallk-Dominating Sets and Applications
