Graph algorithms and graph partitioning

III SUMMARY Master Thesis Graph Algorithms and Graph Partitioning Ali KARCI Fırat üniversity Graduate School of Natural and Applied Sciences Department of Computer Engineering 1998, Pages : 100 in this work, graph algorithms and graph partitioning software, satisfied the load balancing conditions, has been developed. The load balancing can be defined as each processor get equl work and transmission among processors is minimum. in this work, graph partitioning haz been analyzed mostly. If vertices of graph have coordinate, then vertices of graph are sorted with respect to specified axis and they are partitioned into two parts. I f they do not have coordinate, then Laplace matrix of graph is used to partition graph ör graph is partitioned randomly. The advantages and disadvantages of methods have been given by comparison of methods. KEYWORDS :Spectral graphpartitioning, randomgraph partitioning, simple graphreduction, multilevelgraph partitioning,load balancing,network partitioning,circuit partitioning.