Search research articles

ABOUT JoVE

Overview Leadership Blog JoVE Help Center

AUTHORS

Publishing Process Editorial Board Scope & Policies Peer Review FAQ Submit

LIBRARIANS

Testimonials Subscriptions Access Resources Library Advisory Board FAQ

RESEARCH

JoVE Journal Methods Collections JoVE Encyclopedia of Experiments Archive

EDUCATION

JoVE Core JoVE Business JoVE Science Education JoVE Lab Manual Faculty Resource Center Faculty Site

Terms & Conditions of Use

Related Concept Videos

Vector Algebra: Graphical Method

Vector Algebra: Graphical Method

Vectors can be multiplied by scalars, added to other vectors, or subtracted from other vectors. The vector sum of two (or more) vectors is called the resultant vector or, for short, the resultant.
We use the laws of geometry to construct resultant vectors, followed by trigonometry to find vector magnitudes and directions. For a geometric construction of the sum of two vectors in a plane, we follow the parallelogram rule. Suppose two vectors are at arbitrary positions. Translate either one of...

pV-Diagrams

pV-Diagrams

The pV diagram, which is a graph of pressure versus volume of the gas under study, is helpful in describing certain aspects of the substance. When the substance behaves like an ideal gas, the ideal gas equation describes the relationship between its pressure and volume. On a pV diagram, it is common to plot an isotherm, which is a curve showing p as a function of V with the number of molecules and the temperature fixed. Then, for an ideal gas, the product of the pressure of the gas and its...

Karyotyping

Karyotyping

Block Diagram Reduction

Block Diagram Reduction

The process of deriving the transfer function of a control system often involves reducing its block diagram to a single block. This simplification can be achieved through a series of strategic operations, including relocating branch points and comparators. These operations preserve the overall function of the system while allowing for easier manipulation and combination of blocks.
The first step in this process is the identification and relocation of a branch point. A branch point, where a...

Bewley Lattice Diagram

Bewley Lattice Diagram

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.

Ogive Graph

Ogive Graph

An ogive graph is sometimes called a cumulative frequency polygon. It is one type of frequency polygon that shows cumulative frequency. In other words, the cumulative percentages are added to the graph from left to right. An ogive graph plots cumulative frequency on the vertical y-axis and class boundaries along the horizontal x-axis. It’s very similar to a histogram; only instead of rectangles, an ogive displays a single point where the top right of the rectangle would be. Creating this...

You might also read

Related Articles

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

Sort by

Same authorSame journal

Near-optimal distributed dominating set in bounded arboricity graphs.

Distributed computing·2024

Same author

Redundancy in distributed proofs.

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

See all related articles

Search research articles

Related Experiment Video

Updated: Oct 14, 2025

Revealing Neural Circuit Topography in Multi-Color

Revealing Neural Circuit Topography in Multi-Color

Published on: November 14, 2011

Improved distributed -coloring.

Mohsen Ghaffari¹, Juho Hirvonen², Fabian Kuhn³

¹ETH Zurich, Zürich, Switzerland.

Distributed Computing

|November 1, 2021

Summary

This summary is machine-generated.

New randomized distributed algorithms achieve graph coloring in fewer rounds. These algorithms improve upon a 25-year-old state-of-the-art method, getting closer to theoretical lower bounds for graph coloring complexity.

More Related Videos

Accurate and Simple Evaluation of Vascular Anastomoses in Monochorionic Placenta using Colored Dye

Accurate and Simple Evaluation of Vascular Anastomoses in Monochorionic Placenta using Colored Dye

Published on: September 5, 2011

Author Spotlight: Emerging Technologies and Advanced Tools for Decoding Metabolomics Data Analysis

Author Spotlight: Emerging Technologies and Advanced Tools for Decoding Metabolomics Data Analysis

Published on: November 10, 2023

Related Experiment Videos

Last Updated: Oct 14, 2025

Revealing Neural Circuit Topography in Multi-Color

Revealing Neural Circuit Topography in Multi-Color

Published on: November 14, 2011

Accurate and Simple Evaluation of Vascular Anastomoses in Monochorionic Placenta using Colored Dye

Accurate and Simple Evaluation of Vascular Anastomoses in Monochorionic Placenta using Colored Dye

Published on: September 5, 2011

Author Spotlight: Emerging Technologies and Advanced Tools for Decoding Metabolomics Data Analysis

Author Spotlight: Emerging Technologies and Advanced Tools for Decoding Metabolomics Data Analysis

Published on: November 10, 2023

Area of Science:

Computer Science
Distributed Computing
Graph Theory

Background:

Graph coloring is a fundamental problem in computer science with applications in resource allocation and scheduling.
Existing randomized distributed algorithms for graph coloring have limitations in terms of the number of rounds required.
The state-of-the-art algorithm by Panconesi and Srinivasan (1993) has remained unbeaten for 25 years.

Purpose of the Study:

To develop improved randomized distributed algorithms for graph coloring.
To reduce the number of rounds required for computing a valid graph coloring.
To approach the theoretical lower bounds for distributed graph coloring.

Main Methods:

Development of a randomized distributed algorithm for computing a (Delta)-coloring in non-complete graphs.
Design of a randomized algorithm for computing a (Delta+1)-coloring when Delta is small.
Analysis of the number of rounds required by the proposed algorithms.

Main Results:

A new randomized distributed algorithm achieves (Delta)-coloring in O(log n) rounds for non-complete graphs.
A second randomized algorithm computes a (Delta+1)-coloring in O(log n) rounds when Delta is small.
Both algorithms significantly improve upon the previous O(log n) round state-of-the-art algorithm, reducing the number of rounds required.

Conclusions:

The presented algorithms offer substantial improvements in the efficiency of distributed graph coloring.
The new algorithms bring the practical performance closer to theoretical limits, advancing the field of distributed graph algorithms.