A Fast and Effective Algorithm for the Feedback Arc Set Problem

• Berger, B. and P.W. Shor. (1990). “Approximation Algorithms for the Maximum Acyclic Subgraph Problem.” In Proc. First ACM-SIAM Symp. Discrete Algorithms. pp. 236–243.

• Calazans, Ney, et al. (1992). “Advanced Ordering and Manipulation Techniques for Binary Decision Diagrams.” In European Design Automation Conference, Brussels, Belgium. pp. 452–457.

• Cormen, T., C. Leiserson, and R. Rivest. (1990). Introduction to Algorithms. Cambridge, Mass: The MIT Press.

  Google Scholar 

• De Souza, C., R. Keunings, L. Wolsey, and O. Zone. (1994). “A New Approach to Minimizing the Frontwidth in Finite Element Calculations.” Computer Methods in Applied Mechanics and Engineering 111(3/4), 323–334.

  Google Scholar 

• Eades, P. and X. Lin. (To appear). “AHeuristic for the Feedback Arc Set Problem.”Australasian J. of Combinatorics.

• Eades, P., X. Lin, and W.F. Smyth. (1993). “A Fast and Effective Heuristic for the Feedback Arc Set Problem.” Inf. Proc. Lett. 47, 319–323.

  Google Scholar 

• Eades, P., W.F. Smyth, and X. Lin. (1989). “Heuristics for the Feedback Arc Set Problem.” Tech. Rept. 1, School of Computing Science, Curtin University of Technology, Perth, Western Australia.

  Google Scholar 

• Ford, L. and D. Fulkerson. (1962). Flows in Networks. Princeton, NJ: Princeton University Press.

  Google Scholar 

• Garey, M.R. and D.S. Johnson. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York, NY: W. H. Freeman and Company.

  Google Scholar 

• Goldberg, A. and R. Tarjan. (1986). “A New Approach to the Maximum Flow Problem.” In Proc. Eight ACM Symp. on Theory of Computing. pp. 136–146.

• Lempel, A. and I. Cederbaum. (1966). “Minimum Feedback Arc and Vertex Sets of a Directed Graph.” IEEET Trans. Circuit TheoryCT-13(4), 399–403.

  Google Scholar 

• Lucchesi, C.L. (1976). “A Minimax Equality For Directed Graphs.” Doctoral Thesis, University of Waterloo, Ontario, Canada.

  Google Scholar 

• Lucchesi, C.L. and D.H. Younger. (1978). “A Minimax Theorem For Directed Graphs.” J. London Math. Soc. 2(17), 369–374.

  Google Scholar 

• Mitra, B., P. Ranjan Panda, and P. Pal Chaudhuri. (1993). “Estimating the Complexity of Synthesized Designs from FSM Specifications.” IEEE Design & Test of Computers 10(1), 30–35.

  Google Scholar 

• Cherabuddi, Raghava V. and Magdy A. Bayoumi. (1994). “Automated System Partitioning for Synthesis of Multi-Chip Modules.” In Fourth Great Lakes Symposium on VLSI, Design Automation of High Performance VLSI Systems. pp. 21–25.

• Ramachandran, V. (1988). “Finding Minimum Feedback Arc Set in Reducible Flow graphs.” J. Algorithms 9, 299–313.

  Google Scholar 

• Saab, Y. (1990). “Combinatorial Optimization by Stochastic Evolution with Applications to the Physical Design of VLSI Circuits”. Doctoral Thesis, University of Illinois at Urbana-Champaign.

  Google Scholar 

• Saab, Y. (1993). “Post-Analysis-Based Clustering Dramatically Improves the Fiduccia-Mattheyses Algorithm.” In European Design Automation Conference, Hamburg, Germany. pp. 22–27.

• Saab, Y. (1995). “A Fast and Robust Network Bisection Algorithm.” IEEE Trans. Computers 44(7), 903–913.

  Google Scholar 

• Saab, Y. and V. Rao. (1991). “Combinatorial Optimization by Stochastic Evolution.” IEEE Trans. Computer-Aided Design 10(4), 525–535.

  Google Scholar 

• Seshu, S. and M.B. Reed. (1961). Linear Graphs and Electrical Networks. Reading, Mass: Addison Wesley.

  Google Scholar 

• Slater, P. (1971). “Optimal Ranking of Tournaments.” Networks 1, 135–138.

  Google Scholar 

• Unger, S.H. (1957). “A Study of Asynchronous Logical Feedback Networks.” Tech. Rept. 320, Research Lab. of Electronics, MIT, Cambridge, Mass.

  Google Scholar 

• Younger, D.H. (1963). “Minimum Feedback Arc Sets for a Directed Graph.” IEEE Trans. Circuit Theory CT-10, 238–245.

  Google Scholar 

Download references