Powered by OpenAIRE graph
Found an issue? Give us feedback
addClaim

A Prim Minimum Spanning Tree Algorithm for Directed Graph

방향 그래프의 Prim 최소신장트리 알고리즘
Authors: Myeong-Bok Choi; Sang-Un Lee;

A Prim Minimum Spanning Tree Algorithm for Directed Graph

Abstract

Abstract This paper suggests an algorithm that obtains the Minimum Spanning Tree for directed graph (DMST). The existing Chu-Liu/Edmonds DMST algorithm has chances of the algorithm not being able to find DMST or of the sum of ST not being the least. The suggested algorithm is made in such a way that it always finds DMST, rectifying the disadvantage of Chu-Liu/Edmonds DMST algorithm. Firstly, it chooses the Minimum- Weight Arc (MWA) from all the nodes including a root node, and gets rid of the nodes in which cycle occurs after sorting them in an ascending order. In this process, Minimum Spanning Forest (MST) is obtained. If there is only one MSF, DMST is obtained. And if there are more than 2 MSFs, to determine MWA among all MST nodes, it chooses a method of directly calculating the sum of all the weights, and hence simplifies the emendation process for solving a cycle problem of Chu-Liu/Edmonds DMST algorithm. The suggested Sulee DMST algorithm can always obtain DMST that minimizes the weight of the arcs no matter if the root node is set or not, and it is also capable to find the root node of a graph with minimized weight.

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    2
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
2
Average
Average
Average
Upload OA version
Are you the author of this publication? Upload your Open Access version to Zenodo!
It’s fast and easy, just two clicks!