NDLI: A Parallel Implementation of Gomory-Hu's Cut Tree Algorithm

Content Provider	IEEE Xplore Digital Library
Author	Cohen, J. Rodrigues, L.A. Duarte, E.P.
Copyright Year	2012
Abstract	Cut trees are a compact representation of the edge-connectivity between every pair of vertices of an undirected graph, and have a large number of applications. In this work a parallel version of the well known Gomory-Hu cut tree algorithm is presented. The parallel strategy is based on the master/slave model. The strategy is optimistic in the sense that the master process manipulates the tree being constructed and the slaves solve minimum s-t-cuts independently. Another version is proposed that employs a heuristic that enumerates all (up to a limit) of the minimum s-t-cuts in order to choose the most balanced one. The algorithm was implemented and extensive experimental results are presented, including a comparison with Gusfieldâs cut tree algorithm. Parallel versions of these algorithms have achieved significant speedups on real and synthetic graphs. We discuss the trade-offs between the two alternatives, each of which presents better results given the characteristics of the input graph. In particular, the existence of balanced cuts clearly gives an advantage to Gomory-Huâsalgorithm.
Starting Page	124
Ending Page	131
File Size	236953
Page Count	8
File Format	PDF
ISBN	9781467347907
ISSN	15506533
e-ISBN	9780769549071
DOI	10.1109/SBAC-PAD.2012.37
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2012-10-24
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Partitioning algorithms Educational institutions Erbium Clustering algorithms Informatics Electronic mail Contracts parallel algorithms Cut trees
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

A Novel Clustering Algorithm for Graphs

Image segmentation using graph cut technique for outdoor scene images

Cut Tree Algorithms (1999)

Cut Tree Algorithms (1999)

An improved parallel minimum spanning tree based clustering algorithm for microarrays data analysis

Correlation k-Clustering in Trees and Trees of Rings

Research and application of fuzzy-clustering algorithm based on pretreatment of similarity relation

An asynchronous parallel genetic algorithm for the maximum likelihood phylogenetic tree search

A half-split grid clustering algorithm by simulating cell division

A Parallel Implementation of Gomory-Hu's Cut Tree Algorithm

Similar Documents

A Novel Clustering Algorithm for Graphs

Image segmentation using graph cut technique for outdoor scene images

Cut Tree Algorithms (1999)

Cut Tree Algorithms (1999)

An improved parallel minimum spanning tree based clustering algorithm for microarrays data analysis

Correlation k-Clustering in Trees and Trees of Rings

Research and application of fuzzy-clustering algorithm based on pretreatment of similarity relation

An asynchronous parallel genetic algorithm for the maximum likelihood phylogenetic tree search

A half-split grid clustering algorithm by simulating cell division

A Parallel Implementation of Gomory-Hu's Cut Tree Algorithm