Name
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. |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1016/0166-218X(94)00042-C | Discrete Applied Mathematics |
Field | DocType | Volume |
Discrete mathematics,Complete graph,Combinatorics,Vertex (geometry),Reversing,Bipartite graph,Cycle graph,Directed graph,Directed acyclic graph,Mathematics,Digraph | Journal | 60 |
Issue | ISSN | Citations |
1-3 | Discrete Applied Mathematics | 10 |
PageRank | References | Authors |
2.14 | 8 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jean-Pierre Barthélemy | 1 | 149 | 16.42 |
| Olivier Hudry | 2 | 659 | 64.10 |
| Garth Isaak | 3 | 172 | 24.01 |
| Fred S. Roberts | 4 | 527 | 85.71 |
| Barry Tesman | 5 | 10 | 2.14 |