Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Concept Videos

Incomplete Dominance01:43

Incomplete Dominance

21.6K
Gregor Mendel's work (1822 - 1884) was primarily focused on pea plants. Through his initial experiments, he determined that every gene in a diploid cell has two variants called alleles inherited from each parent. He suggested that amongst these two alleles, one allele is dominant in character and the other recessive. The combination of alleles determines the phenotype of a gene in an organism.
21.6K
Distributed Loads: Problem Solving01:21

Distributed Loads: Problem Solving

624
Beams are structural elements commonly employed in engineering applications requiring different load-carrying capacities. The first step in analyzing a beam under a distributed load is to simplify the problem by dividing the load into smaller regions, which allows one to consider each region separately and calculate the magnitude of the equivalent resultant load acting on each portion of the beam. The magnitude of the equivalent resultant load for each region can be determined by calculating...
624
Norton's Theorem01:14

Norton's Theorem

523
Norton's theorem is a fundamental principle stating that a linear two-terminal circuit can be substituted with an equivalent circuit, which comprises a current source (ⅠN) in parallel with a resistor (RN). Here, ⅠN represents the short-circuit current flowing through the terminals, and RN stands for the input or equivalent resistance at the terminals when all independent sources are deactivated. This implies that the circuit illustrated in Figure (a) can be exchanged with the...
523
Lattice Centering and Coordination Number02:33

Lattice Centering and Coordination Number

9.5K
The structure of a crystalline solid, whether a metal or not, is best described by considering its simplest repeating unit, which is referred to as its unit cell. The unit cell consists of lattice points that represent the locations of atoms or ions. The entire structure then consists of this unit cell repeating in three dimensions. The three different types of unit cells present in the cubic lattice are illustrated in Figure 1.
Types of Unit Cells
Imagine taking a large number of identical...
9.5K
Routh-Hurwitz Criterion II01:19

Routh-Hurwitz Criterion II

192
In the application of the Routh-Hurwitz criterion, two specific scenarios can arise that complicate stability analysis.
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
192
Bewley Lattice Diagram01:12

Bewley Lattice Diagram

549
The Bewley lattice diagram, developed by L. V. Bewley, effectively organizes the reflections occurring during transmission-line transients. It visually represents how voltage waves propagate and reflect within a transmission line, making it easier to understand the complex interactions that occur.
549

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Improved distributed <math></math> -coloring.

Distributed computing·2021
Same journal

A topological characterization of stabilizing consensus.

Distributed computing·2026
Same journal

Connectivity Labeling in Faulty Colored Graphs.

Distributed computing·2026
Same journal

Optimal message-passing with noisy beeps.

Distributed computing·2025
Same journal

Asymmetric distributed trust.

Distributed computing·2024
Same journal

Component stability in low-space massively parallel computation.

Distributed computing·2024
Same journal

Equivalence classes and conditional hardness in massively parallel computations.

Distributed computing·2022
See all related articles

Related Experiment Video

Updated: Jun 7, 2025

Quantitative Analysis of Neuronal Dendritic Arborization Complexity in Drosophila
07:13

Quantitative Analysis of Neuronal Dendritic Arborization Complexity in Drosophila

Published on: January 7, 2019

14.0K

Near-optimal distributed dominating set in bounded arboricity graphs.

Michal Dory1, Mohsen Ghaffari2, Saeed Ilchi3

  • 1Department of Computer Science, University of Haifa, Haifa, Israel.

Distributed Computing
|November 11, 2024
PubMed
Summary
This summary is machine-generated.

We developed a deterministic distributed algorithm for approximating the minimum weighted dominating set problem. This algorithm achieves a near-optimal round complexity, improving upon previous results for both weighted and unweighted graphs.

Keywords:
Approximation algorithmsArboricityDistributed computingDominating set

More Related Videos

Quantifying Corticolous Arthropods Using Sticky Traps
05:28

Quantifying Corticolous Arthropods Using Sticky Traps

Published on: January 19, 2020

5.4K
Inherent Dynamics Visualizer, an Interactive Application for Evaluating and Visualizing Outputs from a Gene Regulatory Network Inference Pipeline
10:44

Inherent Dynamics Visualizer, an Interactive Application for Evaluating and Visualizing Outputs from a Gene Regulatory Network Inference Pipeline

Published on: December 7, 2021

2.1K

Related Experiment Videos

Last Updated: Jun 7, 2025

Quantitative Analysis of Neuronal Dendritic Arborization Complexity in Drosophila
07:13

Quantitative Analysis of Neuronal Dendritic Arborization Complexity in Drosophila

Published on: January 7, 2019

14.0K
Quantifying Corticolous Arthropods Using Sticky Traps
05:28

Quantifying Corticolous Arthropods Using Sticky Traps

Published on: January 19, 2020

5.4K
Inherent Dynamics Visualizer, an Interactive Application for Evaluating and Visualizing Outputs from a Gene Regulatory Network Inference Pipeline
10:44

Inherent Dynamics Visualizer, an Interactive Application for Evaluating and Visualizing Outputs from a Gene Regulatory Network Inference Pipeline

Published on: December 7, 2021

2.1K

Area of Science:

  • Distributed Algorithms
  • Graph Theory
  • Approximation Algorithms

Background:

  • The minimum weighted dominating set problem is a fundamental problem in graph theory with applications in network design and facility location.
  • Existing distributed algorithms for this problem have limitations in terms of approximation ratios or round complexity, especially for weighted graphs.

Purpose of the Study:

  • To design a simple deterministic distributed algorithm for approximating the minimum weighted dominating set.
  • To analyze the round complexity and approximation factor of the proposed algorithm.
  • To establish lower bounds on the round complexity for this problem.

Main Methods:

  • A deterministic distributed algorithm with a specific round complexity is presented.
  • The algorithm's performance is analyzed for graphs with bounded arboricity.
  • A reduction from the KMW lower bound for distributed vertex cover approximation is used to establish a lower bound for the dominating set problem.

Main Results:

  • A deterministic O(log n) round distributed algorithm achieving an O(log Δ) approximation for minimum weighted dominating set on graphs with arboricity at most O(log n) is developed.
  • A nearly optimal lower bound on the round complexity is proven, even for the unweighted case.
  • The algorithm improves upon existing randomized and deterministic approximation algorithms in terms of round complexity and approximation factor.

Conclusions:

  • The proposed deterministic algorithm offers a significant improvement in round complexity for approximating the minimum weighted dominating set.
  • The established lower bound highlights the near-optimality of the algorithm's round complexity.
  • Further research includes a randomized algorithm with an improved approximation factor, demonstrating tightness in the first order due to NP-hardness.