Name
Title | ||
|---|---|---|
Acyclic Orientations for Deadlock Prevention in Interconnection Networks (Extended Abstract) |
Abstract | ||
|---|---|---|
In this paper we extend some of the computational results presented in [6] on finding an acyclic orientation of a graph which minimizes the maximum number of changes of orientations along the paths connecting a given subset of source-destination couples. The corresponding value is called rank of the set of paths. Besides its theoretical interest, the topic has also practical applications. In fact, the existence of a rank r acyclic orientation for a graph implies the existence of a deadlock-free routing strategy for the corresponding network which uses at most r buffers per vertex. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1007/BFb0024487 | WG |
Keywords | Field | DocType |
routing and communication in interconnection networks,computational and structural complexity,deadlock prevention,par- allel algorithms,interconnection networks,extended abstract,graph theory,acyclic orientations | Acyclic dependencies principle,Discrete mathematics,Combinatorics,Computer science,Deadlock prevention algorithms,Interconnection | Conference |
ISBN | Citations | PageRank |
3-540-63757-5 | 2 | 0.39 |
References | Authors | |
9 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jean-claude Bermond | 1 | 595 | 83.74 |
| Miriam di Ianni | 2 | 144 | 17.27 |
| Michele Flammini | 3 | 681 | 70.12 |
| Stephane Perennes | 4 | 433 | 48.60 |