A Minimax Arc Theorem for Reducible Flow Graphs

TitleA Minimax Arc Theorem for Reducible Flow Graphs
Publication TypeTechnical Report
Year of Publication1987
AuthorsRamachandran, V.
Other Numbers484
Abstract

We establish a conjecture of Frank and Gyarfas by proving that the cardinality of a minimum feedback arc set in a reducible flow graph is equal to the cardinality of a maximum collection of arc disjoint cycles.

URLhttp://www.icsi.berkeley.edu/pubs/techreports/tr-87-001.pdf
Bibliographic Notes

ICSI Technical Report TR-87-001

Abbreviated Authors

V. Ramachandran

ICSI Publication Type

Technical Report