PhD Theses

Permanent URI for this collection

Now showing 1 - 1 of 1

Development of algorithms for list colouring problems using random graphs
(University of Dar es Salaam, 2015) Mkandawile, Mashaka James
The Thesis was concerned with scheduling problems where a schedule was a Latin rectangle and each cell in the Latin rectangle was filled by an allowed symbol from the list of symbols available in that cell. It was observed from literature that list colouring problems using small list size have not been explored to date. Therefore this research used random graphs to develop heuristics algorithms for scheduling purposes. Findings indicated the existence of heuristic algorithms for estimating the list size and for computing the asymptotic probabilities in random (depleted) graph. Findings also indicated that when a constant p>0 was selected and given n vertices and Latin row r such that r<121-2pn then the Latin rectangle was produced with a probability of at least 1-2n+2e-pn16. Lastly findings provided a recursive procedure for building Latin rectangles row by row in an n×n array of randomly assigned sets chosen such that for all cells, the independent probability of any of the n symbols occurring in the cell is exactly p>0.