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

Show simple item record

dc.contributor.author Isaak, Garth en_US
dc.contributor.author Narayan, Darren en_US
dc.date.accessioned 2007-09-13T02:09:27Z en_US
dc.date.available 2007-09-13T02:09:27Z en_US
dc.date.issued 2003 en_US
dc.identifier.citation Journal of Graph Theory 45N1 (2003) 28-47 en_US
dc.identifier.issn 0364-9024 en_US
dc.identifier.uri http://hdl.handle.net/1850/4709 en_US
dc.description RIT community members may access full-text via RIT Libraries licensed databases: http://library.rit.edu/databases/
dc.description.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. en_US
dc.description.sponsorship This paper was written as part of Darren A. Narayan’s PhD thesis at Lehigh University under the direction of Garth Isaak. The authors thank the Reidler Foundation for partial support of this work. They further thank David Zimmerli for assistance with computer simulations that provided the insight that led to the discovery of Theorem 2.1. en_US
dc.language.iso en_US en_US
dc.publisher John Wiley & Sons, Ltd en_US
dc.relation.ispartofseries vol. 45 en_US
dc.relation.ispartofseries no. 1 en_US
dc.subject Feedback arc sets en_US
dc.subject Linear ordering problem en_US
dc.subject Tournaments en_US
dc.title Complete classification of tournaments having a disjoint union of directed paths as a minimum feedback arc set en_US
dc.type Article en_US
dc.identifier.url http://dx.doi.org/10.1002/jgt.10155

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 simple item record

Search RIT DML


Advanced Search

Browse