Development of algorithms for list colouring problems using random graphs

Simple item page
dc.contributor.authorMkandawile, Mashaka James
dc.date.accessioned2019-11-23T11:58:05Z
dc.date.accessioned2020-01-07T15:46:50Z
dc.date.available2019-11-23T11:58:05Z
dc.date.available2020-01-07T15:46:50Z
dc.date.issued2015
dc.description: Available in print form, East Africana Collection, Dr. Wilbert Chagula Library, Class mark (THS EAF QA166.17M552)en_US
dc.description.abstractThe 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.en_US
dc.identifier.citationMkandawile, M. J.(2015).Development of algorithms for list colouring problems using random graphs, Doctoral dissertation, University of Dar es Salaam.en_US
dc.identifier.urihttp://localhost:8080/xmlui/handle/123456789/1951
dc.language.isoenen_US
dc.publisherUniversity of Dar es Salaamen_US
dc.subjectAlgorithmsen_US
dc.subjectRandom graphsen_US
dc.titleDevelopment of algorithms for list colouring problems using random graphsen_US
dc.typeThesisen_US

Files

Collections

PhD Theses