본문 바로가기
  • Home

An Algorithm for Minimum Feedback Edge Set Problem

  • Journal of The Korea Society of Computer and Information
  • Abbr : JKSCI
  • 2015, 20(3), pp.107-113
  • Publisher : The Korean Society Of Computer And Information
  • Research Area : Engineering > Computer Science

Sang-Un, Lee 1

1강릉원주대학교

Accredited

ABSTRACT

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.

Citation status

* References for papers published after 2022 are currently being built.