» Introduction
» Definitions
» Cut tree algorithms
» Publications
» Source code
» Dataset
» Contact
|
|
Introduction
- This page contains information about
parallel implementations of cut tree
algorithms using MPI and OpenMP. This
information is supplementary to the papers
listed below. Source code is provided.
Keywords: Cut tree
algorithms, parallel graph algorithms,
MPI, OpenMP.
|
Definitions:
Flow Equivalent Trees and Cut Trees
- A flow equivalent tree is
a compact representation of the
edge-connectivity between every pair of
vertices of an undirected graph. Formally:
given an undirected capacitated graph
G=(V,E), a flow equivalent tree of
G is a capacitated tree T=(V, ET)
that satisfies:
- For all u,v ∈ V, λ(u, v, G) = λ(u,
v, T), where λ(u, v, G) and λ(u, v,
T) denote the edge-connectivity between u
and v in G and T, respectively. In
other words, λ(u, v, G) is the capacity of
a minimum u-v-edge-cut.
- A cut tree of G is a flow
equivalent tree T=(V,ET) that
satisfies:
- For all u,v ∈ V, the cut produced by
removing an edge of minimum weight from
the path between u and v in T corresponds
to a minimum u-v-cut of G.
|
Cut
tree algorithms
Two cut tree
algorithms for weighted undirected graphs are
well known: the Gomory-Hu’s algorithm and
Gusfield’s algorithm. Both algorithms make n −
1 calls to a maximum flow algorithm. The
algorithms differ in their data structure:
while the former algorithm contracts the
original graph, the latter computes all cuts
on the input graph. See the paper below for
details.
|
| Main Publications
|
- Jaime
Cohen, Luiz A. Rodrigues, Elias
P. Duarte Jr., "Parallel
Cut Tree Algorithms",
Journal of Parallel and
Distributed Computing, ISSN
0743-7315, pp. 1-14, Vol. 109,
2017
Abstract:
In this work three parallel cut
tree algorithms are presented,
including parallel versions of
Gusfield and Gomory-Hu
algorithms. A hybrid algorithm
that combines techniques from
both algorithms is proposed
which provides a more robust
performance for arbitrary
instances. Experimental results
show that the three algorithms
achieve significant speedups on
real and synthetic graphs. We
discuss the trade-offs between
the alternatives, each of which
presents better results given
the characteristics of the input
graph. On several instances the
hybrid algorithm outperformed
both other algorithms, being
faster than the parallel
Gomory-Hu algorithm on most
instances.
- Jaime
Cohen,
Luiz A. Rodrigues, Fabiano Silva,
Renato Carmo, Andre Guedes, Elias
P. Duarte Jr.,
"Parallel Implementations
of Gusfield's Cut Tree
Algorithm",
11th
International
Conference Algorithms and
Architectures for Parallel
Processing (ICA3PP),
pp. 258-269, Lecture
Notes
in Computer Science (LNCS) 7016,
ISSN 0302-9743, Melbourne,
Australia, 2011.
Download: PDF
Errata: here
Abstract: This
paper presents parallel versions
of Gusfield’s cut tree
algorithm. Cut trees are a
compact representation of the
edge-connectivity between every
pair of vertices of an
undirected graph. Cut trees have
many applications in
combinatorial optimization and
in the analysis of networks
originated in many applied
fields. However, surprisingly
few works have been published on
the practical performance of cut
tree algorithms. This paper
describes two parallel versions
of Gusfield’s cut tree algorithm
and presents extensive
experimental results which show
a significant speedup on most
real and synthetic graphs in our
dataset.
- Jaime
Cohen, Luiz A. Rodrigues, Elias P.
Duarte Jr.,
"A
Parallel Implementation of
Gomory-Hu's Cut Tree Algorithm",
The 24th International Symposium
on Computer Architecture and High
Performance Computing
(SBAC-PAD'2012),
New York, U.S.A., 2012. Download:
PDF
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’s algorithm.
|
|
| Source code:
|
- Parallel Gusfield Algorithm
- OpenMP
(flow equivalent tree version)
- MPI (flow
equivalent tree version)
- Parallel Gomory-Hu Algorithm
- Hybrid Parallel Gomory-Hu Algorithm
|
Dataset:
|
| Contact: |
- Jaime Cohen
e-mail: 
|
|
|
