Algorithms for balanced graph bi-partitioning

Conference item


Wu, J., Jiang, G., Zheng, L. and Zhou, S. 2014. Algorithms for balanced graph bi-partitioning. 2014 IEEEInternational Conference on High Performance Computing and Communications (HPCC). Paris, France 20 - 22 Aug 2014 Institute of Electrical and Electronics Engineers (IEEE). pp. 185-188 https://doi.org/10.1109/HPCC.2014.35
TitleAlgorithms for balanced graph bi-partitioning
AuthorsWu, J., Jiang, G., Zheng, L. and Zhou, S.
Abstract

Graph partitioning has been widely applied in cloud computing, data centers, virtual machine scheduling, hardware/software co-design, and VLSI circuit design, etc. The general graph partitioning problem is known to be NP-hard. This paper investigates how to partition the vertex set of an undirected weighted graph into two disjoint subsets, such that the total vertex-weights of the two subsets are nearly equal, and the total weight of the edges connecting the two subsets is minimized. A heuristic algorithm is proposed to initialize an approximate bipartition such that the total vertex-weight of each subset is close to that of the other. The proposed algorithm constructs a subset by selecting a group of neighboring vertices with the highest gain from the original graph for inclusion into the subset. A customized tabu search is proposed to further refine the initial partition, which minimizes the communication cost and keeps partition balanced. Experimental results show that the proposed algorithms outperform the state-of-the-art on the public benchmarks, with the improvement of up to 79% for certain cases.

Conference2014 IEEEInternational Conference on High Performance Computing and Communications (HPCC)
Page range185-188
Proceedings Title2014 IEEEInternational Conference on High Performance Computing and Communications (HPCC)
ISBN
Hardcover9781479961221
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Publication dates
Print2014
Publication process dates
Deposited18 Sep 2015
Accepted20 Aug 2014
Output statusPublished
Digital Object Identifier (DOI)https://doi.org/10.1109/HPCC.2014.35
LanguageEnglish
Book title2014 IEEE Intl Conf on High Performance Computing and Communications, 2014 IEEE 6th Intl Symp on Cyberspace Safety and Security, 2014 IEEE 11th Intl Conf on Embedded Software and Syst (HPCC,CSS,ICESS),
Permalink -

https://repository.mdx.ac.uk/item/8546y

  • 12
    total views
  • 0
    total downloads
  • 0
    views this month
  • 0
    downloads this month

Export as