Conferences in Research and Practice in Information Technology
  

Online Version - Last Updated - 20 Jan 2012

 

 
Home
 

 
Procedures and Resources for Authors

 
Information and Resources for Volume Editors
 

 
Orders and Subscriptions
 

 
Published Articles

 
Upcoming Volumes
 

 
Contact Us
 

 
Useful External Links
 

 
CRPIT Site Search
 
    

A Contraction Algorithm for finding Minimal Feedback Sets

Koehler, H.

    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 transformation 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 flow graphs, as it preserves the structure and can easily be combined with the algorithm proposed by Ramachandran (Ramachandran 1988).
Cite as: Koehler, H. (2005). A Contraction Algorithm for finding Minimal Feedback Sets. In Proc. Twenty-Eighth Australasian Computer Science Conference (ACSC2005), Newcastle, Australia. CRPIT, 38. Estivill-Castro, V., Ed. ACS. 165-174.
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS
 

 

ACS Logo© Copyright Australian Computer Society Inc. 2001-2014.
Comments should be sent to the webmaster at crpit@scem.uws.edu.au.
This page last updated 16 Nov 2007