Volume 10 Number 1 (Jan. 2015)
Home > Archive > 2015 > Volume 10 Number 1 (Jan. 2015) >
JSW 2015 Vol.10(1): 94-105 ISSN: 1796-217X
doi: 10.17706/jsw.10.1.94-105

The Shortest Path Algorithms of Hypergraphs Based on Search Strategies

Xinquan Chen1, 2
1School of Computer Science & Engineering, Chongqing Three Gorges University, Chongqing, China.
2Web Sciences Center, University of Electronic Science & Technologhy of China, Chengdu, China.


Abstract—In order to search the shortest path from hypergraphs with unweighted hyperedges, a kind of searching algorithm based on the width-first strategy is presented at first. For hypergraphs with weighted hyperedges, a kind of searching algorithm based on the minimum-cost-first strategy to search the shortest path is presented. In order to enhance the reliability of the two algorithms, their correctness is proven in theory. The ideas and outlines of the two algorithms are illuminated by using two examples. Through the simulation of some artificial hypergraphs, the two algorithms are compared in time cost and the average percentage between the number of nodes in branching trees and the number of all nodes. We find that they can get the same average percentage. This result is consistent with the actual instance. In the end, it gives a research expectation to disinter and popularize the two algorithms.

Index Terms—Hypergraph, minimum-cost-first, shortest path, width-first.

[PDF]

Cite: Xinquan Chen, "The Shortest Path Algorithms of Hypergraphs Based on Search Strategies," Journal of Software vol. 10, no. 1, pp. 94-105, 2015.

General Information

ISSN: 1796-217X (Online)
Frequency: Monthly
Editor-in-Chief: Prof. Antanas Verikas
Executive Editor: Ms. Yoyo Y. Zhou
Abstracting/ Indexing: DBLP, EBSCO, ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat, etc
E-mail: jsw@iap.org
  • Aug 21, 2019 News!

    Papers published in JSW Vol 14, No 1- Vol 14 No 8 have been indexed by DBLP     [Click]

  • Jun 25, 2019 News!

    Vol.13, No.9 has been indexed by EI (Inspec).   [Click]

  • Aug 01, 2018 News!

    [CFP] 2019 the annual meeting of JSW Editorial Board, ICCSM 2019, will be held in Barcelona, Spain, July 14-16, 2019.   [Click]

  • Jul 10, 2019 News!

    Vol 14, No.8 has been published with online version 4 original aritcles from 2 countries are published in this issue.    [Click]

  • Sep 12, 2019 News!

    Vol 14, No 10 has been published with online version 4 original aritcles from 2 countries are published in this issue      [Click]