The reversing number of a diagraph

Jean Pierre Barthélemy; Olivier Hudry; Garth Isaak; Fred S. Roberts; Barry Tesman

doi:10.1016/0166-218X(94)00042-C

The reversing number of a diagraph

Jean Pierre Barthélemy
, Olivier Hudry
, Garth Isaak
, Fred S. Roberts
, Barry Tesman

ENST Bretagne
Lehigh University
Rutgers University–New Brunswick
Dickinson College

Résultats de recherche: Contribution à un journal › Article › Revue par des pairs

16 Citations (Scopus)

Résumé

A minimum reversing set of a diagraph is a smallest sized set of arcs which when reversed makes the diagraph acyclic. We investigate a related issue: Given an acyclic diagraph D, what is the size of a smallest tournament T which has the arc set of D as a minimun reversing set? We show that such a T always exists and define the reversing number of an acyclic diagraph to be the number of vertices in T minus the number of vertices in D. We also derive bounds and exact values of the reversing number for certain classes of acyclic diagraphs.

langue originale	Anglais
Pages (de - à)	39-76
Nombre de pages	38
journal	Discrete Applied Mathematics
Volume	60
Numéro de publication	1-3
Les DOIs	https://doi.org/10.1016/0166-218X(94)00042-C
état	Publié - 23 juin 1995
Modification externe	Oui

Accès au document

10.1016/0166-218X(94)00042-C

Contient cette citation

@article{0e0d7b3a2b8544c7be33cb32de2e0ba6,

title = "The reversing number of a diagraph",

abstract = "A minimum reversing set of a diagraph is a smallest sized set of arcs which when reversed makes the diagraph acyclic. We investigate a related issue: Given an acyclic diagraph D, what is the size of a smallest tournament T which has the arc set of D as a minimun reversing set? We show that such a T always exists and define the reversing number of an acyclic diagraph to be the number of vertices in T minus the number of vertices in D. We also derive bounds and exact values of the reversing number for certain classes of acyclic diagraphs.",

author = "Barth{\'e}lemy, \{Jean Pierre\} and Olivier Hudry and Garth Isaak and Roberts, \{Fred S.\} and Barry Tesman",

year = "1995",

month = jun,

day = "23",

doi = "10.1016/0166-218X(94)00042-C",

language = "English",

volume = "60",

pages = "39--76",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "1-3",

}

TY - JOUR

T1 - The reversing number of a diagraph

AU - Barthélemy, Jean Pierre

AU - Hudry, Olivier

AU - Isaak, Garth

AU - Roberts, Fred S.

AU - Tesman, Barry

PY - 1995/6/23

Y1 - 1995/6/23

N2 - A minimum reversing set of a diagraph is a smallest sized set of arcs which when reversed makes the diagraph acyclic. We investigate a related issue: Given an acyclic diagraph D, what is the size of a smallest tournament T which has the arc set of D as a minimun reversing set? We show that such a T always exists and define the reversing number of an acyclic diagraph to be the number of vertices in T minus the number of vertices in D. We also derive bounds and exact values of the reversing number for certain classes of acyclic diagraphs.

AB - A minimum reversing set of a diagraph is a smallest sized set of arcs which when reversed makes the diagraph acyclic. We investigate a related issue: Given an acyclic diagraph D, what is the size of a smallest tournament T which has the arc set of D as a minimun reversing set? We show that such a T always exists and define the reversing number of an acyclic diagraph to be the number of vertices in T minus the number of vertices in D. We also derive bounds and exact values of the reversing number for certain classes of acyclic diagraphs.

U2 - 10.1016/0166-218X(94)00042-C

DO - 10.1016/0166-218X(94)00042-C

M3 - Article

AN - SCOPUS:0043142525

SN - 0166-218X

VL - 60

SP - 39

EP - 76

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1-3

ER -

The reversing number of a diagraph

Résumé

Accès au document

Empreinte digitale

Contient cette citation