
handle: 20.500.11850/69344
We present a distributed algorithm for finding a (1 + Ɛ)- approximation of a Minimum Connected Dominating Set in the class of Growth-Bounded graphs, which includes Unit Disk graphs. In addition, the computed Connected Dominating Set guarantees a constant stretch factor on the length of a shortest path with respect to the original graph and induces a subgraph of constant degree. The nodes do not require any positioning or distance information. The algorithm runs in O(TMIS+1/ƐO(1) ċ log* n)synchronous rounds, where TMIS is the time for computing a Maximal Independent Set (MIS) in the network graph. Using the fastest known deterministic algorithm for computing a MIS, the total running time is O((logΔ+1/ƐO(1)) ċ log* n), where Δ is the maximum degree of the network graph. If one allows randomization, the running time reduces to O((log log n+1/ƐO(1))ċ log* n) rounds.
Data processing, computer science, DISTRIBUTED ALGORITHMS + PARALLEL ALGORITHMS (PROGRAMMING METHODS); MOBILE AD HOC NETWORKS + WIRELESS AD HOC NETWORKS (TELECOMMUNICATIONS); VERTEILTE ALGORITHMEN + PARALLELE ALGORITHMEN (PROGRAMMIERMETHODEN); ROUTING (COMPUTER SYSTEMS); MOBILE AD HOC NETZWERKE + DRAHTLOSE AD HOC NETZWERKE (NACHRICHTENTECHNIK); WEGEERMITTLUNG (COMPUTERSYSTEME), Distributed approximation schemes, Growth-bounded graphs, Distributed algorithms, info:eu-repo/classification/ddc/004, Connected dominating sets
Data processing, computer science, DISTRIBUTED ALGORITHMS + PARALLEL ALGORITHMS (PROGRAMMING METHODS); MOBILE AD HOC NETWORKS + WIRELESS AD HOC NETWORKS (TELECOMMUNICATIONS); VERTEILTE ALGORITHMEN + PARALLELE ALGORITHMEN (PROGRAMMIERMETHODEN); ROUTING (COMPUTER SYSTEMS); MOBILE AD HOC NETZWERKE + DRAHTLOSE AD HOC NETZWERKE (NACHRICHTENTECHNIK); WEGEERMITTLUNG (COMPUTERSYSTEME), Distributed approximation schemes, Growth-bounded graphs, Distributed algorithms, info:eu-repo/classification/ddc/004, Connected dominating sets
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
