The week's pick
Random Articles
Reseach Article
Enhanced Multilevel Hybrid Algorithm for Graph Partitioning
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 120 - Number 6 |
| Year of Publication: 2015 |
| Authors: Annu Arora, Karanvir Kaur |
10.5120/21231-3977
|
Annu Arora, Karanvir Kaur . Enhanced Multilevel Hybrid Algorithm for Graph Partitioning. International Journal of Computer Applications. 120, 6 ( June 2015), 16-19. DOI=10.5120/21231-3977
Abstract
Graph partitioning is a traditional problem with many applications and a number of high quality algorithms have been developed. Graph partitioning by multilevel scheme is more popular, which includes three phases coarsening, initial partitioning and uncoarsening. In this paper a road network graph is partitioned into two parts, with the aim of reducing the cut size. In road network graph, the nodes or vertices are road junctions, endpoint, etc. and the edges are the path or road length. Recently multilevel hybrid graph partitioning algorithm was proposed using local search refinement strategy and balanced big method for initial partition. In this paper simulated annealing is used to improve the quality of partition and has given better results.
References
- Sanjeev Arora, Satish Rao, and Umesh Vazirani 2008. Geometry, Flows, and Graph-Partitioning Algorithms ,communications of the acm | October 2008 | vol. 51 | no. 10.
- David S. Johnson 1984. The NP-Completeness Column: An Ongoing Guide Published in J. ALGORITHMS 5, 433-447.
- George Karypis and Vipin Kumar 1998. Multilevel k-way Partitioning Scheme for Irregular Graphs,Journal Of Parallel And Distributed Computing 48, 96–129 Article No. Pc971404.
- George Karypis and Vipin Kumar 1998. A Fast And High Quality Multilevel Scheme For Partitioning Irregular Graphs,Siam J. Sci. Comput. C° 1998 Society for Industrial And Applied Mathematics Vol. 20, No. 1, Pp. 359-392 .
- Isabelle Staton, Gabriel Kliot 2012. Streaming Graph Partitioning for Large Distributed Graphs,ACM
- David S. Johnson,Cecilia R. Aragon,Lyle A. McGeoch and Catherine schevon 1989. Optimization By Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning, Operations Research Society of America ,vol. 37,no. 6.
- Cedric Chevalier and Ilya Safro2009. Comparison of coarsening schemes for multilevel graph partitioning,Sandia National Laboratories, Albuquerque, NM, USA, Ccheval@Sandia. Gov. Argonne National Laboratory, Argonne, IL, USA, Safro@Mcs. Anl. Gov
- Dr. S. Padmavathi, Adline George 2014. Multilevel Hybrid Graph Partitioning Algorithm,department of Computer Science and Engineering Thiagarajar College of Engineering Madurai, India
- Dimitris Bertsimas and John Tsitsiklis 1993,SimulatedAnnealing,Statistical sciences vol. 8,no. 1, 10-15
- Florian Bourse, Marc Lelarge and Milan Vojnovic 2014, Balanced Graph Edge Partition, Microsoft Reasearch.
- L. Tao,Y. C. Zhao,K. Thulasiraman and M. N. S Swamy 1992,Simulated Annealing and Tabu Search Algorithms for Multiway Graph Partition, Journal of circuits,systems and computers
- Somayeh Sobati moghadam 2013 ,New algorithm for automatic visualization of metro map, International Journal of Computer Science vol. 10.
- Scott Kirkpatrick (1984),Optimization by Simulated Annealing : Quantitative Studies, Journal of Statistical Physics vol 34.
- Daniel Delling_, Andrew V. Goldberg_, Ilya Razenshteyn_x, and Renato F. Werneck 2011. Graph Partitioning with Natural Cuts Microsoft Research Silicon Valley Mountain View, CA, 94043, USA.
- Emmanouil Spanakis, Christodoulos Efstathiades, George Pallis Marios and D. Dikaiakos 2011. Real-Time Graph Visualization Tool for Vehicular Ad-Hoc Networks, Real-Time Graph Visualization Tool for Vehicular Ad-Hoc Networks .
Index Terms
Keywords