Deadlock prevention by acyclic orientations

Description

In this paper we consider a combinatorial problem consisting in finding an acyclic orientation of a graph which minimizes the maximum number of changes of orientations along a given set of dipaths. A change of orientation along a dipath occurs when two consecutive arcs are discordly oriented. Such maximum number of changes of orientations is called the rank of the acyclic orientation with respect to the set of dipaths and the minimum rank of all possible acyclic orientations is the rank of the graph with respect to the set of dipaths. Besides its theoretical interest, the topic has also practical applications. In fact,

Abstract

International audience

Additional details