A contraction algorithm for finding minimal feedback sets

Koehler, Henning (2005). A contraction algorithm for finding minimal feedback sets. In: , Proceedings of ACSC 2005. Twenty Eighth Australasian Computer Science Conference (ACSC 2005), Newcastle, NSW, Australia., (165-174). 30 January - 3 February, 2005.


Author Koehler, Henning
Title of paper A contraction algorithm for finding minimal feedback sets
Conference Paper Type Fully Published Paper
Conference name Twenty Eighth Australasian Computer Science Conference (ACSC 2005)    (ERA 2010 Rank B)
Conference location Newcastle, NSW, Australia.
Conference dates 30 January - 3 February, 2005
Proceedings title Proceedings of ACSC 2005
Publication date 2005
ISBN 1-920682-20-1
Start page 165
End page 174
Total pages 10
Language eng
Abstract/Summary We present a contraction algorithm for finding a minimal set of arcs or vertices that break all cycles in a digraph. The algorithm is (essentially) an extension to the contraction algorithm for the feedback vertex set problem introduced by Levy and Lew (Levy & Lew 1988). The algorithm's time complexity of O (mlog n) is preserved, while allowing both (weighted) feedback vertices and arcs. As the trans- formation from feedback arc set to feedback vertex set graph increases the graph's size, the new algorithm becomes both faster and more powerful than the original one when applied to feedback arc set problems. We will show that the algorithm works well for reducible °ow graphs, as it preserves the structure and can easily be combined with the algorithm proposed by Ramachandran (Ramachandran 1988).
Subjects 0906 Electrical and Electronic Engineering
Q-Index Code EX

Document type: Conference Paper
Sub-type: Fully Published Paper
Collection: School of Information Technology and Electrical Engineering Publications
 
Versions
Version Filter Type
Citation counts: Google Scholar Search Google Scholar
Access Statistics: 25 Abstract Views  -  Detailed Statistics
Created: Mon, 08 Mar 2010, 13:07:17 EST by Ms Lynette Adams on behalf of Faculty Of Engineering, Architecture & Info Tech