Scheduling static tasks on parallel architectures is a basic problem arising in the design of parallel algorithms. This NP-complete problem has been widely investigated in the literature and remains one of the most challenging questions in the field. Among the resolution methods for this type of problems, the taboo search technique is of particular interest. Based on this technique, two algorithms are proposed and tested on a sample of instances in order to be compared experimentally with other well-known algorithms. The results clearly indicate good overall performances of our algorithms. Next, some NP-completeness results are established showing that this problem is intractable for approximation, even for some restricted cases bearing a clear relation to the instances treated experimentally in this work.

\( X \)-proper edge colourings of bipartite graphs are defined. These colourings arise in timetables where rooms have to be assigned to courses. The objective is to minimize the number of different rooms in which each course must be taught. An optimum assignment is represented by a \( k \)-optimum edge colouring of a bipartite graph. Some necessary conditions for a \( k \)-optimum colouring are obtained, in terms of forbidden subgraphs. An algorithm based on removing these forbidden subgraphs to obtain improved colourings is described.

A graph \( G \) of order \( n \) is pancyclic if it contains a cycle of length \( \ell \) for every \( \ell \) such that \( 3 \leq \ell \leq n \). If the graph is bipartite, then it contains no cycles of odd length. A balanced bipartite graph \( G \) of order \( 2n \) is bipancyclic if it contains a cycle of length \( \ell \) for every even \( \ell \), such that \( 4 \leq \ell \leq 2n \). A graph \( G \) of order \( n \) is called \( k \)-semipancyclic, \( k \geq 0 \), if there is no “gap” of \( k+1 \) among the cycle lengths in \( G \), i.e., for no \( \ell \leq n-k \) is it the case that each of \( C_\ell, \ldots, C_{\ell+k} \) is missing from \( G \). Generalizing this to bipartite graphs, a bipartite graph \( G \) of order \( n \) is called \( k \)-semibipancyclic, \( k \geq 0 \), if there is no “gap” of \( k+1 \) among the even cycle lengths in \( G \), i.e., for no \( \ell \leq n-2k \) is it the case that each of \( C_{2\ell}, \ldots, C_{2\ell+2k} \) is missing from \( G \).

In this paper we generalize a result of Hakimi and Schmeichel in several ways. First to \( k \)-semipancyclic, then to bipartite graphs, giving a condition for a hamiltonian bipartite graph to be bipancyclic or one of two exceptional graphs. Finally, we give a condition for a hamiltonian bipartite graph to be \( k \)-semibipancyclic or a member of a very special class of hamiltonian bipartite graphs.

We consider labeling edges of graphs with elements from abelian groups. Particular attention is given to graphs where the labels on any two Hamiltonian cycles sum to the same value. We find several characterizations for such labelings for cubes, complete graphs, and complete bipartite graphs. This extends work of \([1, 8, 9, 10]\). We also consider the computational complexity of testing if a labeled graph has this property and show it is NP-complete even when restricted to integer labelings of 3-connected, cubic, planar graphs with face girth at least five.