Tournaments with a transitive subtournament as a feedback arc set

Show full item record

Title: Tournaments with a transitive subtournament as a feedback arc set
Author: Baldwin, Jennifer; Kronholm, William; Narayan, Darren
Abstract: Given an acyclic digraph D, we seek a smallest sized tournament T that has D as a minimum feedback arc set. The reversing number of a digraph is defined to be r(D) = |V (T)|−|V (D)| . The case where D is a tournament Tn was studied by Isaak in 1995 using an integer linear programming formulation. In particular, this approach was used to produce lower bounds for r(Tn), and it was conjectured that the given bounds were tight. We examine the class of tournaments where n = 2k +2k−2 and show the known lower bounds for r(Tn) are best possible.
Record URI: http://hdl.handle.net/1850/4725
Date: 2002

Files in this item

Files Size Format View
DNarayanArticle2002.pdf 176.1Kb PDF View/Open

The following license files are associated with this item:

This item appears in the following Collection(s)

Show full item record

Search RIT DML


Advanced Search

Browse