@article{ART001976020},
author={Sang-Un, Lee},
title={An Algorithm for Minimum Feedback Edge Set Problem},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2015},
volume={20},
number={3},
pages={107-113}
TY - JOUR
AU - Sang-Un, Lee
TI - An Algorithm for Minimum Feedback Edge Set Problem
JO - Journal of The Korea Society of Computer and Information
PY - 2015
VL - 20
IS - 3
PB - The Korean Society Of Computer And Information
SP - 107
EP - 113
SN - 1598-849X
AB - This paper presents a polynomial time algorithm to the minimum cardinality feedback edge set andminimum weight feedback edge set problems. The algorithm makes use of the property wherein the sumof the minimum spanning tree edge set and the minimum feedback edge set equals a given graph's edgeset. In other words, the minimum feedback edge set is inherently a complementary set of the former. Theproposed algorithm, in pursuit of the optimal solution, modifies the minimum spanning tree finding Kruskal'salgorithm so as to arrange the weight of edges in a descending order and to assign cycle-deficient edgesto the maximum spanning tree edge set MXST and cycle-containing edges to the feedback edge set FES.
This algorithm runs with linear time complexity, whose execution time corresponds to the number of edgesof the graph. When extensively tested on various undirected graphs both with and without the weighed edge, the proposed algorithm has obtained the optimal solutions with 100% success and accuracy.
KW - Minimumfeedback edge set problem;Weight;Cardinality;Minimumspanning tree
DO -
UR -
ER -
Sang-Un, Lee. (2015). An Algorithm for Minimum Feedback Edge Set Problem. Journal of The Korea Society of Computer and Information, 20(3), 107-113.
Sang-Un, Lee. 2015, "An Algorithm for Minimum Feedback Edge Set Problem", Journal of The Korea Society of Computer and Information, vol.20, no.3 pp.107-113.
Sang-Un, Lee "An Algorithm for Minimum Feedback Edge Set Problem" Journal of The Korea Society of Computer and Information 20.3 pp.107-113 (2015) : 107.
Sang-Un, Lee. An Algorithm for Minimum Feedback Edge Set Problem. 2015; 20(3), 107-113.
Sang-Un, Lee. "An Algorithm for Minimum Feedback Edge Set Problem" Journal of The Korea Society of Computer and Information 20, no.3 (2015) : 107-113.
Sang-Un, Lee. An Algorithm for Minimum Feedback Edge Set Problem. Journal of The Korea Society of Computer and Information, 20(3), 107-113.
Sang-Un, Lee. An Algorithm for Minimum Feedback Edge Set Problem. Journal of The Korea Society of Computer and Information. 2015; 20(3) 107-113.
Sang-Un, Lee. An Algorithm for Minimum Feedback Edge Set Problem. 2015; 20(3), 107-113.
Sang-Un, Lee. "An Algorithm for Minimum Feedback Edge Set Problem" Journal of The Korea Society of Computer and Information 20, no.3 (2015) : 107-113.
