In this paper an algorithm to generate edge-colouring
schemes for graphs, which needs
at most 
colours, is implemented. The problem of minimising the sum of
the largest weight of each colour is looked at and an algorithm
which attempts to solve the problem has been suggested.
The algorithms were used to organise communication for irregular grid applications. The optimised algorithm REDUCE10 was found to improve the communication time of the synchronous communication scheme. Synchronous and asynchronous communication schemes were also compared and it was confirmed that the latter reduces the total elapsed time of a finite element code even further, at the expense of increased memory usage.
The algorithm for edge-colouring, and the new algorithm for minimise the sum of largest weight of each colour, are generic graph theory algorithms and can be used for other applications. One possible application is in the parallel algorithms for mesh partitioning and dynamic load balancing. This will be the subject of further investigation.
Acknowledgment
This work is sponsored by ICI PLC through a collaborative project with the Advanced Research Computing Group at Daresbury Laboratory.