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

Second Uniqueness Theorem

Second Uniqueness Theorem

Consider a region consisting of several individual conductors with a definite charge density in the region between these conductors. The second uniqueness theorem states that if the total charge on each conductor and the charge density in the in-between region are known, then the electric field can be uniquely determined.
In contrast, consider that the electric field is non-unique and apply Gauss's law in divergence form in the region between the conductors and the integral form to the...

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

Wilcoxon Signed-Ranks Test for Matched Pairs

Wilcoxon Signed-Ranks Test for Matched Pairs

The Wilcoxon signed-rank test for matched pairs evaluates the null hypothesis by combining the ranks of differences with their signs. It essentially tests whether the median of the differences in a population of matched pairs is zero. Since the test incorporates more information than the sign test, it generally yields more trustable conclusions. This test also does not require the data to follow a normal distribution, but two conditions must be met for it to be applicable: (1) the data must...

Woodward–Hoffmann Selection Rules and Microscopic Reversibility

Woodward–Hoffmann Selection Rules and Microscopic Reversibility

Electrocyclic reactions, cycloadditions, and sigmatropic rearrangements are concerted pericyclic reactions that proceed via a cyclic transition state. These reactions are stereospecific and regioselective. The stereochemistry of the products depends on the symmetry characteristics of the interacting orbitals and the reaction conditions. Accordingly, pericyclic reactions are classified as either symmetry-allowed or symmetry-forbidden. Woodward and Hoffmann presented the selection criteria for...

Parallel Processing

Parallel Processing

The brain processes sensory information rapidly due to parallel processing, which involves sending data across multiple neural pathways at the same time. This method allows the brain to manage various sensory qualities, such as shapes, colors, movements, and locations, all concurrently. For instance, when observing a forest landscape, the brain simultaneously processes the movement of leaves, the shapes of trees, the depth between them, and the various shades of green. This enables a quick and...

Sign Test for Matched Pairs

Sign Test for Matched Pairs

The sign test for matched pairs offers a robust method for comparing two paired samples, often for the effects of an intervention in one of them. This method is very useful in situations where the underlying distribution of the data is unknown. The test compares two related samples—often pre- and post-treatment measurements on the same subjects—to determine if there are significant differences in their median values.
To conduct the sign test, we first calculate the differences in...

You might also read

Related Articles

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

Sort by

Same author

Extension of Molecular Exchange Monte Carlo for the Prediction of Liquid-Liquid Equilibria in Gibbs Ensemble Monte Carlo Simulations.

The journal of physical chemistry. B·2025

Same authorSame journal

Parallel Maximum Cardinality Matching for General Graphs on GPUs.

IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum : [proceedings]. IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum·2024

Same author

py-MCMD: Python Software for Performing Hybrid Monte Carlo/Molecular Dynamics Simulations with GOMC and NAMD.

Journal of chemical theory and computation·2022

Same author

Complex Left Atrial Appendage Morphology Is an Independent Risk Factor for Cryptogenic Ischemic Stroke.

Frontiers in cardiovascular medicine·2018

Same author

Impact of Interdisciplinary Outpatient Specialty Palliative Care on Survival and Quality of Life in Adults With Advanced Cancer: A Meta-Analysis of Randomized Controlled Trials.

Annals of behavioral medicine : a publication of the Society of Behavioral Medicine·2018

Same author

Molecular exchange Monte Carlo: A generalized method for identity exchanges in grand canonical Monte Carlo simulations.

The Journal of chemical physics·2018

Same journal

Developing Distributed High-performance Computing Capabilities of an Open Science Platform for Robust Epidemic Analysis.

IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum : [proceedings]. IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum·2025

Same journal

Sequre: a high-performance framework for rapid development of secure bioinformatics pipelines.

IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum : [proceedings]. IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum·2022

Same journal

Application of Distributed Agent-based Modeling to Investigate Opioid Use Outcomes in Justice Involved Populations.

IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum : [proceedings]. IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum·2022

Same journal

TurboBFS: GPU Based Breadth-First Search (BFS) Algorithms in the Language of Linear Algebra.

IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum : [proceedings]. IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum·2022

Same journal

Optimizing High-Performance Computing Systems for Biomedical Workloads.

IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum : [proceedings]. IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum·2020

See all related articles

Search research articles

Related Experiment Video

Updated: Jun 17, 2025

Quadruple-Checkerboard: A Modification of the Three-Dimensional Checkerboard for Studying Drug Combinations

Quadruple-Checkerboard: A Modification of the Three-Dimensional Checkerboard for Studying Drug Combinations

Published on: July 24, 2021

Shared-Memory Parallel Edmonds Blossom Algorithm for Maximum Cardinality Matching in General Graphs.

Gregory Schwing¹, Daniel Grosu¹, Loren Schwiebert¹

¹Department of Computer Science, Wayne State University, Detroit, MI.

IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum : [Proceedings]. IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum

|August 9, 2024

Summary

This summary is machine-generated.

This study optimized the Edmonds Blossom algorithm for faster graph matching. Parallel processing with coarse-grain locking significantly reduced runtime on various graph types, improving efficiency for complex network analysis.

Keywords:

Edmonds Blossom general graphs matching parallel

More Related Videos

Large-scale Reconstructions and Independent, Unbiased Clustering Based on Morphological Metrics to Classify Neurons in Selective Populations

Large-scale Reconstructions and Independent, Unbiased Clustering Based on Morphological Metrics to Classify Neurons in Selective Populations

Published on: February 15, 2017

A Psychophysics Paradigm for the Collection and Analysis of Similarity Judgments

A Psychophysics Paradigm for the Collection and Analysis of Similarity Judgments

Published on: March 1, 2022

Related Experiment Videos

Last Updated: Jun 17, 2025

Quadruple-Checkerboard: A Modification of the Three-Dimensional Checkerboard for Studying Drug Combinations

Quadruple-Checkerboard: A Modification of the Three-Dimensional Checkerboard for Studying Drug Combinations

Published on: July 24, 2021

Large-scale Reconstructions and Independent, Unbiased Clustering Based on Morphological Metrics to Classify Neurons in Selective Populations

Large-scale Reconstructions and Independent, Unbiased Clustering Based on Morphological Metrics to Classify Neurons in Selective Populations

Published on: February 15, 2017

A Psychophysics Paradigm for the Collection and Analysis of Similarity Judgments

A Psychophysics Paradigm for the Collection and Analysis of Similarity Judgments

Published on: March 1, 2022

Area of Science:

Computer Science
Graph Theory
Algorithm Optimization

Background:

The Edmonds Blossom algorithm is a fundamental method for finding maximum matchings in general graphs.
Existing implementations using depth-first search are inherently serial and can be computationally intensive.
There is a need for faster and more efficient algorithms for graph matching, especially for large and complex networks.

Purpose of the Study:

To develop a faster, parallelized implementation of the Edmonds Blossom algorithm.
To investigate the performance gains achievable through code streamlining and parallelization techniques.
To evaluate the algorithm's effectiveness on different types of graphs, including random and real-world networks.

Main Methods:

Implemented the Edmonds Blossom algorithm using a streamlined, serial approach.
Introduced parallelism by extracting computations across algorithm iterations using coarse-grain locking.
Tested the optimized algorithm on random regular graphs and real-world graphs with varying densities and community structures.

Main Results:

The streamlined serial implementation was 3-5 times faster than previous general graph matching codes.
Parallelization with coarse-grain locking achieved a four-fold runtime reduction on random regular graphs and a two-fold reduction on real-world graphs.
Sparse graphs with community structures showed a three-fold slowdown with eight threads, but this was overcome by marginal speedups on graphs with an average degree greater than four.

Conclusions:

The parallel coarse-grain locking implementation of the Edmonds Blossom algorithm demonstrates significant performance improvements.
This approach is effective for extracting parallelism from augmenting-path-based algorithms.
The findings suggest that this parallel implementation may be suitable for similar graph-based algorithms and complex network analysis.