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

An efficient parallel algorithm for shortest paths in planar layered digraphs.

P K Mishra1

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

Journal of Zhejiang University. Science
|April 15, 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 planar layered digraphs. It achieves logarithmic time complexity using a novel divide and conquer approach and a one-way separator.

Area of Science:

  • Computer Science
  • Algorithm Analysis
  • Parallel Computing

Background:

  • The shortest path problem is a fundamental challenge in graph theory with numerous applications.
  • Existing algorithms for planar layered digraphs may not scale efficiently on parallel architectures.
  • Efficient parallel solutions are crucial for handling large-scale graph problems.

Purpose of the Study:

  • To develop an efficient parallel algorithm for the shortest path problem in planar layered digraphs.
  • To achieve a time complexity significantly better than existing parallel approaches.
  • To introduce a novel algorithmic technique for pathfinding in specific graph structures.

Main Methods:

  • A divide and conquer strategy is employed to break down the problem into smaller subproblems.

Related Experiment Videos

  • A novel 'one-way separator' concept is introduced, ensuring paths are crossed only once.
  • The algorithm is designed for parallel execution utilizing n processors.

    • Main Results:

    • The proposed algorithm achieves an optimal time complexity of O(log3n) on n processors.
    • Demonstrates significant efficiency gains for shortest path computations in planar layered digraphs.
    • The one-way separator technique proves effective in parallel pathfinding.

    Conclusions:

    • The developed parallel algorithm offers a highly efficient solution for the shortest path problem in planar layered digraphs.
    • The novel one-way separator is a key innovation enabling the algorithm's performance.
    • This work advances the field of parallel graph algorithms and shortest path computation.