We use the textbook of Bondy and Murty [1]} for terminology and notation we do not specify here.
Throughout, unless we specify explicitly that we consider other types of graphs, all graphs we consider are labelled acyclic directed multigraphs, i.e., they may have multiple arcs. Such graphs consist of a vertex set \(V\)  (representing the states of a process), an arc set \(A\)  (representing the actions, i.e., transitions from one state to another), a set of labels \(L\)  (in our applications in fact a set of label pairs, each representing a type of action and the worst case duration of its execution), and two mappings.
The first mapping \(\mu : A\rightarrow V\times V\)  is an incidence function that identifies the tail and head of each arc \(a\in A\) .
In particular, \(\mu (a)=(u,v)\)  means that the arc \(a\)  is directed from \(u\in V\)  to \(v\in V\) , where \(tail(a)=u\)  and \(head(a)=v\) . We also call \(u\)  and \(v\)  the ends of \(a\) .
The second mapping \(\lambda :A\rightarrow L\)  assigns a label pair \(\lambda (a)=(\ell (a),t(a))\)  to each arc \(a\in A\) , where \(\ell (a)\)  is a string representing the (name of an) action and \(t(a)\)  is the weight of the arc \(a\) .
This weight \(t(a)\)  is a real positive number representing the worst case execution time of the action represented by \(\ell (a)\) .
