The reversing number of a digraph
type: Item
instance of: scholarly article
title: The reversing number of a digraph
zbMATH Open document ID: 0826.05032
DOI: 10.1016/0166-218X(94)00042-C
author: Olivier Hudry
author: Garth Isaak
author: J. P. Barthélemy
author: Fred Roberts
author: Barry A. Tesman
published in: Discrete Applied Mathematics
publication date: 1995-09-06T00:00:00Z
review text: Given an acyclic digraph \(D\), the authors investigate the problem of determining the size of the smallest tournament \(T\) which has the arc set of \(D\) as a minimum reversing set. A minimum reversing set of a digraph is a smallest set of arcs which, when reversed, make a digraph acyclic. It is shown that there exists a smallest sized \(T\) which has an arc set of \(D\) as a minimum reversing set. Bounds are determined and exact values of the reversing sets for several special classes of acyclic digraphs are established.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 777814
zbMATH Keywords: reversing number
zbMATH Keywords: acyclic digraph
zbMATH Keywords: tournament
zbMATH Keywords: minimum reversing set
reviewed by: David P. Brown
MaRDI profile type: Publication
cites work: Matrices and Sequences
cites work: Q5650707
cites work: Q4055664
cites work: Cycles in digraphs– a survey
cites work: Q4198785
cites work: On the maximum cardinality of a consistent set of arcs in a random tournament
cites work: On Sets of Consistent Arcs in a Tournament
cites work: A Cutting Plane Algorithm for the Linear Ordering Problem
cites work: On the acyclic subgraph polytope
cites work: On the degrees of the vertices of a directed graph
cites work: Parallel concepts in graph theory
cites work: SERIATION USING ASYMMETRIC PROXIMITY MEASURES
cites work: Q4028497
cites work: Q3221421
cites work: Q4142699
cites work: Approximative Algorithms for Discrete Optimization Problems
cites work: On the maximal order of cyclicity of antisymmetric directed graphs
cites work: Q3215236
cites work: Q5585195
cites work: On Sets of Arcs Containing No Cycles in a Tournament*
cites work: Disproof of a conjecture of Erdös and moser on tournaments
cites work: Maximum-likelihood paired comparison rankings
cites work: Q3338254
cites work: Q3285875
cites work: Optimal ranking of tournaments
cites work: Optimally ranking unrankable tournaments
cites work: Rankings from Paired Comparisons
description: scientific article; zbMATH DE number 777814