A Minimax Arc Theorem for Reducible Flow Graphs
SIAM Journal on Discrete MathematicsPublished 1 November 1990
Vijaya Ramachandran
Citations22
SJR quartileQ1
SJR score1.09
SNIP1.23
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A conjecture of Frank and Gyarfas is established by proving that the cardinality of a minimum feedback arc set in a reducible flow graph is equal to the cardinalities of a maximum collection of arc disjoint cycles.
Abstract
A conjecture of Frank and Gyarfas is established 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.
Keywords
Computer ScienceMathematics
Society for Industrial and Applied Mathematics eBooksData Structures and Network Algorithms
2,067 Citations1983Robert E. Tarjan
This paper presents a meta-trees tree model that automates the very labor-intensive and therefore time-heavy and therefore expensive process of manually selecting trees to grow in a graph.
Journal of the ACMCharacterizations of Reducible Flow Graphs
168 Citations1974Matthew S. Hecht, Jeffrey D. Ullman
The backward edges of a reducible flow graph are unique and it is shown that there is a “natural” single-entry loop associated with each backward edge of a reducing flow graph.
Journal of AlgorithmsFinding a minimum feedback arc set in reducible flow graphs
52 Citations1988Vijaya Ramachandran
It is shown that any algorithm that solves the FAS problem or the vertex-weighted FVS problem on reducible flow graphs has time complexity at least that of finding a minimum cut in a flow network, for which the best algorithms currently known have time complexity.