Complete classification of tournaments having a disjoint union of directed paths as a minimum feedback arc set

Show full item record

Title: Complete classification of tournaments having a disjoint union of directed paths as a minimum feedback arc set
Author: Isaak, Garth; Narayan, Darren
Abstract: A feedback arc set of a digraph is a set of arcs whose reversal makes the resulting digraph acyclic. Given a tournament with a disjoint union of directed paths as a feedback arc set, we present necessary and sufficient conditions for this feedback arc set to have minimum size. We will present a construction for tournaments where the difference between the size of a minimum feedback arc set and the size of the largest collection of arc disjoint cycles can be made arbitrarily large. We will also make a connection to a problem found in [Barthélemy et al., [2]]. The reversing number of a digraph was defined to be where T is a smallest tournament having the arc set of D as a minimum feedback arc set. As a consequence of our classification of all tournaments having a disjoint union of directed paths as a minimum feedback arc set, we will obtain a new result involving the reversing number. We obtain precise reversing numbers for all digraphs consisting of a disjoint union of directed paths.
Description: RIT community members may access full-text via RIT Libraries licensed databases: http://library.rit.edu/databases/
Record URI: http://hdl.handle.net/1850/4709
Publishers URL: http://dx.doi.org/10.1002/jgt.10155
Date: 2003

Files in this item

Files Size Format View

An open access version of this file is not available. Check "Publisher URL" field for access

This item appears in the following Collection(s)

Show full item record

Search RIT DML


Advanced Search

Browse