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 | |