En Kısa Yol Probleminde Çizge Parçalama Yöntemi Kullanılarak Yeni Bir Yaklaşım

Bu çalışmada ilk olarak çizge kuramının temel kavramları verilmiş, en kısa yol problemi tanıtılmış ve ayrıca çizge parçalama için Kernighan Lin algoritması ele alınmıştır. Asıl amaç olarak, en kısa yol problemi için çizgeyi Kernighan Lin algoritması kurallarına göre işlemcilere ayıran ve böylelikle problem için çizgeyi başlangıç ve bitiş noktalarını ele alan bir zincir çizge formuna dönüştürerek en kısa yolu bulan bir yaklaşım ortaya konulmuştur. Her parça içinde amaç düğümler arasındaki en kısa rotayı bulan parça içi en kısa yollar hesaplanmaktadır.

An Approach for the Shortest Path Problem: Dealing With Graph Partitioning

As a starting point of this study, basic concepts of graph theory, shortest path problem, and Kernighan Lin algorithm are presented for graph partitioning problem. Main aim is to present an approach which solves the shortest path problem by using the graph partitioning technique in regard with the rules of Kernighan-Lin algorithm; therefore it becomes to a chain graph dealing with the starting and the target nodes of the problem. The shortest paths are calculated in order to provide the shortest route between the objective nodes in all the processors.

PDF

___

Berger, M.J., Bokhari, S.H. (1987), A Partitioning Strategy for Non- Uniform Problems across Multiprocessors, IEEE Transactions on Computers, C-36:570-580.
Berkeley, C.S. (1996), “Lectures Graph Partitioning I,II,.” HTTP, CS267, Ders Notları
Buckley, F., Harary, F. (1990), Distance in Graphs, California: Addison-Wesley Pub.
Bui, T.N., Moon, B.R. (1996), Genetic algorithm and graph partitioning, IEEE Transactions on Computers, 45(7):841-855.
Dündar, S., Beşer, M.K., Dündar, P. (2000), En Kısa Yol Probleminin Çizge Parçalanışı ile Çözümü, Yöneylem Araştırması ve Endüstri Mühendisliği XXI. Ulusal Kongresi Bildiriler Kitabı, 118–121
Fjalström, P. (1998), Algorithms for Graph Partitioning, Linköping University Electronic Press
Fiduccia, C., Mattheyses, R. A (1982), Linear time heuristic for improving network partitions, 19th IEEE Design Automation Conference
Gilbert, J.R., Zmijewski, E. (1987), A parallel graph partitioning algorithm for a message-passing multiprocessor”. International J. of Parallel Programming 16(1), 427-449.
Miller, G.L., Teng, S.H., Thurston, W., Vavasis, S.A. (1993), Automatic mesh partitioning, In A. George, .R. Gilbert, and J.W.H. Liu, editors, Graph Theory and Sparse Matrix Computation, volume 56 of The IMA Volumes in Mathematics and its Applications, 57-84. SpringerVerlag.
Pothen, A. Simon, H.D., Liu, K.P. (1990), Partitioning sparse matrices with eigenvectors of graphs, SIAM J. on Matrix Analysis and Applications 11(3), 430-452.
Rolland, H. Pirkul, Glover, F. (1996), Tabu search for graph partitioning, Ann. Oper. Res., 63, 209-232.
Schloegel, K., Karypis, G.,  Kumar, V. (1997), Parallel multilevel difusion schemes for repartitioning of adaptive meshes. Technical Report 97-014, University of Minnesota, Department of Computer Science.
Walshaw, C., Cross, M.,  Everett, M.G. (1997), Parallel dynamic graph-partitioning for unstructured meshes. Technical Report 97/IM/20, University of Greenwich, Centre for Numerical Modelling and Process Analysis.