✦ LIBER ✦

Fast Distributed Construction of Smallk-Dominating Sets and Applications

✍ Scribed by Shay Kutten; David Peleg

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 312 KB
Volume: 28
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1998.0929

No coin nor oath required. For personal study only.

✦ Synopsis

This article presents a fast distributed algorithm to compute a small k-dominat-Ž . Ž ing set D for any fixed k and to compute its induced graph partition breaking . the graph into radius k clusters centered around the vertices of D . The time Ž . complexity of the algorithm is O k log* n . Small k-dominating sets have applications in a number of areas, including routing with sparse routing tables, the design of distributed data structures, and center selection in a distributed network. The main application described in this article concerns a fast distributed algorithm for Ž . constructing a minimum-weight spanning tree MST . On an n-vertex network of ' Ž . diameter d, the new algorithm constructs an MST in time O n log* n q d , improving on previous results.

📜 SIMILAR VOLUMES

The Chebyshev fast Gauss and nonuniform

The Chebyshev fast Gauss and nonuniform fast Fourier transforms and their application to the evaluation of distributed heat potentials

✍ Shravan K. Veerapaneni; George Biros 📂 Article 📅 2008 🏛 Elsevier Science 🌐 English ⚖ 767 KB

We present a method for the fast and accurate computation of distributed heat potentials in two dimensions. The distributed source is assumed to be given in terms of piecewise space-time Chebyshev polynomials. We discretize uniformly in time, whereas in space the polynomials are defined on the leaf

On distribution function description of

On distribution function description of probabilistic sets and its application in decision making

✍ Ernest Czogałla 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 406 KB

On the construction of a fast constant f

On the construction of a fast constant fraction trigger with integrated circuits and application to various photomultipliertubes

✍ M.R. Maier; P. Sperr 📂 Article 📅 1970 🏛 Elsevier Science ⚖ 410 KB

Values of minors of some infinite famili

Values of minors of some infinite families of matrices constructed from supplementary difference sets and their application to the growth problem

✍ C. Koukouvinos; M. Mitrouli; Jennifer Seberry 📂 Article 📅 2005 🏛 Elsevier Science 🌐 English ⚖ 262 KB

Distributed basis sets of s-type Gaussia

Distributed basis sets of s-type Gaussian functions for molecular electronic structure calculations: Applications of the Gaussian cell model to one-electron polycentric linear molecular systems

✍ S. Wilson 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 799 KB

## I A particular formulation of the distributed Gaussian basis-set approach, the extended Gaussian cell model, is applied to the simplest polycentric molecule, the linear H:+ ion. Calculations of the total energy using two extensions of the original Gaussian cell model are described and results a

Construction of probability distribution

Construction of probability distributions in high dimension using the maximum entropy principle: Applications to stochastic processes, random fields and random matrices

✍ Christian Soize 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 321 KB

## Abstract The construction of probabilistic models in computational mechanics requires the effective construction of probability distributions of random variables in high dimension. This paper deals with the effective construction of the probability distribution in high dimension of a vector‐valu