 |
RUTCOR Colloquia - September 30, 2004
Speaker: GARTH ISAAK
Affiliation: Department of Mathematics, Lehigh University, Bethlehem, PA
Title: Feedback Arc Digraphs
Time: 1:30 - 2:30 PM
Location: RUTCOR Building - Room 139, Rutgers University, Busch Campus,
Piscataway, NJ
Abstract: We look at the problem of determining which tournaments have a
given acyclic digraph as a minimum feedback arc set. The speaker first was
introduced to this problem 15 years ago while a student at RUTCOR. We give some
recent results describing the tournaments that have a smaller acyclic
tournament as a minimum feedback arc set as well as those with a disjoint
union of directed paths as a feedback arc set. The first result shows that the
smallest size of such a tournament is given by the solution to a particular
integer linear programming problem. The second explicitly constructs tournaments
with a gap between the maximum number of arcs disjoint cycles and the minimum
size of a feedback arc set.
Back to Seminars Page.
Back to RUTCOR homepage.
|
