NDLI: Multilevel hybrid graph partitioning algorithm

Content Provider	IEEE Xplore Digital Library
Author	Padmavathi, S. George, A.
Copyright Year	2014
Description	Author affiliation: Dept. of Comput. Sci. & Eng., Thiagarajar Coll. of Eng., Madurai, India (Padmavathi, S.; George, A.)
Abstract	Balanced graph partition is a type of graph partitioning problem that divides the given graph into components, such that the components are of about the same size and there are few connections between the components. The existing approaches partition the graph initially in a random manner which has a very high impact on determining the final quality of the solution. Recently, Multilevel Partitioning methods are proven to be faster among other approaches. This paper proposes a multilevel hybrid algorithm for balanced graph partitioning. Here graph is initially partitioned using Balanced Big method in order to improve the initial solution quality. Further, the quality of the obtained solution is improved using local search refinement procedure. The experimental results indicate that the relatively good initial partitions, when subjected to local search techniques like tabu search and hill climbing, results in better solutions. The experimental results also indicate that for the proposed approach, when the number of partitions increase (are high), the quality of the solution is better than the currently available solutions reported in the existing approaches.
Sponsorship	IEEE India Counc. C Chapt.
Starting Page	85
Ending Page	89
File Size	207686
Page Count	5
File Format	PDF
e-ISBN	9781479925728
DOI	10.1109/IAdCC.2014.6779299
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2014-02-21
Publisher Place	India
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Algorithm design and analysis Random Initial Partition Conferences solution quality Benchmark testing Refinement Data structures Educational institutions Hill Climbing Partitioning algorithms Local Search
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in