» 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, 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
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
|
Dataset:
|
| Contact: |
- Jaime Cohen
e-mail: 
|
|
|
