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...

Theorems of Pappus and Guldinus: Problem Solving

Theorems of Pappus and Guldinus: Problem Solving

Pappus and Guldinus's theorems are powerful mathematical principles that are used for finding the surface area and volume of composite shapes. For example, consider a cylindrical storage tank with a conical top. Finding the surface area or volume can be challenging for such complex shapes. These theorems are particularly useful in calculating the volume and surface area of such systems. Here, the cylindrical storage tank with a conical top can be broken down into two simple shapes: a...

Statically Indeterminate Problem Solving

Statically Indeterminate Problem Solving

Statically indeterminate problems are those where statics alone can not determine the internal forces or reactions. Consider a structure comprising two cylindrical rods made of steel and brass. These rods are joined at point B and restrained by rigid supports at points A and C. Now, the reactions at points A and C and the deflection at point B are to be determined. This rod structure is classified as statically indeterminate as the structure has more supports than are necessary for maintaining...

Castigliano's Theorem: Problem Solving

Castigliano's Theorem: Problem Solving

The deflection of a simply supported beam that carries a central point load can be analyzed using structural mechanics principles, particularly by applying Castigliano's theorem. This theorem relates the displacement at the load application point to the partial derivatives of the strain energy in the structure. The simply supported beam with a point load at its center has symmetric reaction forces at the supports, each bearing half of the load. The bending moment at any point along the beam...

SFG Algebra

SFG Algebra

In Signal Flow Graph (SFG) algebra, the value a node represents is determined by the sum of all signals entering that node. This summed value is then transmitted through every branch leaving the node, making the SFG a powerful tool for visualizing and analyzing control systems.
Each node in an SFG corresponds to a variable, and the interactions between nodes are represented by branches with associated gains. When multiple branches lead into a node, the value at that node is the sum of the...

Fast Decoupled and DC Powerflow

Fast Decoupled and DC Powerflow

The fast decoupled power flow method addresses contingencies in power system operations, such as generator outages or transmission line failures. This method provides quick power flow solutions, essential for real-time system adjustments. Fast decoupled power flow algorithms simplify the Jacobian matrix by neglecting certain elements, leading to two sets of decoupled equations:

You might also read

Related Articles

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

Sort by

Same journal

Generators for Discrete Polynomial L<sub>1</sub> Approximation Problems.

Journal of research of the National Bureau of Standards (1977)·2021

Same journal

Room Temperature Poling of Poly(Vinylidene Fluoride) with Deposited Metal Electrodes.

Journal of research of the National Bureau of Standards (1977)·2021

Same journal

Molecular Dynamics Study of Liquid Rubidium and the Lennard-Jones Fluid.

Journal of research of the National Bureau of Standards (1977)·2021

Same journal

Isoionic Isotope Exchange with Hydroxylapatite and the Dilution Effect.

Journal of research of the National Bureau of Standards (1977)·2021

Same journal

Observations of Surface Changes in Platinum Crucibles.

Journal of research of the National Bureau of Standards (1977)·2021

Same journal

Theory of Flow-Induced Fibril Formation in Polymer Solutions.

Journal of research of the National Bureau of Standards (1977)·2021

See all related articles

Search research articles

Related Experiment Video

Updated: Oct 10, 2025

Temporal Ordering of Dynamic Expression Data from Detailed Spatial Expression Maps

Temporal Ordering of Dynamic Expression Data from Detailed Spatial Expression Maps

Published on: February 9, 2017

A Graph Coloring Algorithm for Large Scheduling Problems.

Frank Thomson Leighton¹

¹Center for Applied Mathematics, National Bureau of Standards Washington, DC 20234.

Journal of Research of the National Bureau of Standards (1977)

|December 9, 2021

Summary

This summary is machine-generated.

A novel graph coloring algorithm demonstrates efficient O(n^2) time complexity for sparse graphs, making it ideal for large-scale scheduling. A new method for generating test graphs aids in evaluating algorithm performance.

Keywords:

05C15 68A10 68A20 90B35 Algorithm chromatic number color function graph graph coloring heuristic interchange random test graphs scheduling time complexity

More Related Videos

Group Synchronization During Collaborative Drawing Using Functional Near-Infrared Spectroscopy

Group Synchronization During Collaborative Drawing Using Functional Near-Infrared Spectroscopy

Published on: August 5, 2022

Revealing Neural Circuit Topography in Multi-Color

Revealing Neural Circuit Topography in Multi-Color

Published on: November 14, 2011

Related Experiment Videos

Last Updated: Oct 10, 2025

Temporal Ordering of Dynamic Expression Data from Detailed Spatial Expression Maps

Temporal Ordering of Dynamic Expression Data from Detailed Spatial Expression Maps

Published on: February 9, 2017

Group Synchronization During Collaborative Drawing Using Functional Near-Infrared Spectroscopy

Group Synchronization During Collaborative Drawing Using Functional Near-Infrared Spectroscopy

Published on: August 5, 2022

Revealing Neural Circuit Topography in Multi-Color

Revealing Neural Circuit Topography in Multi-Color

Published on: November 14, 2011

Area of Science:

Computer Science
Discrete Mathematics
Algorithm Analysis

Background:

Graph coloring is a fundamental problem in computer science with applications in resource allocation.
Existing algorithms face scalability challenges with large and complex graphs.

Purpose of the Study:

Introduce a new graph coloring algorithm.
Evaluate its performance against established methods.
Provide a tool for heuristic evaluation of graph coloring algorithms.

Main Methods:

Developed a novel graph coloring algorithm.
Implemented and compared its performance with existing algorithms.
Created a procedure for generating random test graphs with a known chromatic number.

Main Results:

The new algorithm exhibits O(n^2) time complexity on sparse graphs.
It is particularly effective for large-scale scheduling problems.
Heuristic evaluations using generated test graphs provide insights into algorithm capabilities.

Conclusions:

The proposed graph coloring algorithm offers an efficient solution for sparse graph problems.
Its performance characteristics make it suitable for practical applications like scheduling.
The graph generation procedure is a valuable tool for future algorithm research.