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 Experiment Videos

Optimal parallel algorithm for shortest paths problem on interval graphs.

P K Mishra1

  • 1Department of Applied Mathematics, Birla Institute of Technology, Mesra-Ranchi, 835215, India. pkmishra@ieee.org

Journal of Zhejiang University. Science
|August 24, 2004
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

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

Sort by
Same author

Valorization of Coconut Shell and Blue Berries Seed Waste into Enhance Bacterial Enzyme Production: Co-fermentation and Co-cultivation Strategies.

Indian journal of microbiology·2025
Same author

Diagnostic performance of LR-5 based on hypointensity on Gd-EOB-DTPA-enhanced MRI in the hepatobiliary phase for sHCC using LI-RADS v2018 criteria.

Clinical radiology·2025
Same author

Biotransformation of Raw Mango Seed Waste into Bacterial Hydrolytic Enzymes Enhancement Via Solid State Fermentation Strategy.

Molecular biotechnology·2024
Same author

Soil microbes: a natural solution for mitigating the impact of climate change.

Environmental monitoring and assessment·2023
Same author

Corrigendum to Kinetics investigation of phenolic pollutant degradation via Serratia marcescens ABHI 001 and its application in wastewater treatment [Chemosphere 309P1 (Dec 2022) 136532].

Chemosphere·2023
Same author

Production of fermentable glucose from bioconversion of cellulose using efficient microbial cellulases produced from water hyacinth waste.

International journal of biological macromolecules·2023
Same journal

Enhancing the quality metric of protein microarray image.

Journal of Zhejiang University. Science·2004
Same journal

Mathematical modeling of salt-gradient ion-exchange simulated moving bed chromatography for protein separations.

Journal of Zhejiang University. Science·2004
Same journal

Characterization of cellulose acetate micropore membrane immobilized acylase I.

Journal of Zhejiang University. Science·2004
Same journal

Research on the rheological properties of pesticide suspension concentrate.

Journal of Zhejiang University. Science·2004
Same journal

Ant colony system algorithm for the optimization of beer fermentation control.

Journal of Zhejiang University. Science·2004
Same journal

Scale-up of rifamycin B fermentation with Amycolatoposis mediterranei.

Journal of Zhejiang University. Science·2004
See all related articles

This study introduces an efficient parallel algorithm for solving the shortest-path problem in weighted interval graphs. The algorithm achieves linear time complexity, significantly improving computational efficiency for this graph type.

Area of Science:

  • Computer Science
  • Graph Theory
  • Algorithm Analysis

Background:

  • The shortest-path problem is fundamental in graph theory with numerous applications.
  • Interval graphs present unique structural properties that can be exploited for algorithmic efficiency.
  • Existing algorithms for shortest paths in general graphs may not be optimal for interval graph structures.

Purpose of the Study:

  • To develop an efficient parallel algorithm for the shortest-path problem specifically in weighted interval graphs.
  • To analyze the time complexity of the proposed algorithm.
  • To provide a linear processor CRCW (Concurrent Read, Concurrent Write) algorithm for shortest-path computations in interval graphs.

Main Methods:

  • Design of a parallel algorithm tailored for the interval graph structure.

Related Experiment Videos

  • Implementation of the algorithm using a linear processor CRCW model.
  • Analysis of the algorithm's time and processor complexity.

    • Main Results:

    • An efficient parallel algorithm for the shortest-path problem in weighted interval graphs is presented.
    • The algorithm achieves a time complexity of O(n), where n is the number of intervals.
    • A linear processor CRCW algorithm for shortest-path determination in interval graphs is successfully developed.

    Conclusions:

    • The proposed parallel algorithm offers a significant improvement in efficiency for computing shortest paths in weighted interval graphs.
    • The O(n) time complexity demonstrates the effectiveness of exploiting interval graph properties.
    • This work contributes a valuable tool for graph algorithms and network analysis.