123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393 |
- <?xml version="1.0" encoding="utf-8" ?>
- <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
- <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
- <head>
- <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
- <meta name="generator" content="Docutils 0.6: http://docutils.sourceforge.net/" />
- <title>Parallel BGL Minimum Spanning Tree</title>
- <link rel="stylesheet" href="../../../../rst.css" type="text/css" />
- </head>
- <body>
- <div class="document" id="logo-minimum-spanning-tree">
- <h1 class="title"><a class="reference external" href="http://www.osl.iu.edu/research/pbgl"><img align="middle" alt="Parallel BGL" class="align-middle" src="pbgl-logo.png" /></a> Minimum Spanning Tree</h1>
- <!-- Copyright (C) 2004-2008 The Trustees of Indiana University.
- Use, modification and distribution is subject to the Boost Software
- License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
- http://www.boost.org/LICENSE_1_0.txt) -->
- <p>The Parallel BGL contains four <a class="reference external" href="http://www.boost.org/libs/graph/doc/graph_theory_review.html#sec:minimum-spanning-tree">minimum spanning tree</a> (MST)
- algorithms <a class="citation-reference" href="#dg98" id="id1">[DG98]</a> for use on undirected, weighted, distributed
- graphs. The graphs need not be connected: each algorithm will compute
- a minimum spanning forest (MSF) when provided with a disconnected
- graph.</p>
- <p>The interface to each of the four algorithms is similar to the
- implementation of 'Kruskal's algorithm'_ in the sequential BGL. Each
- accepts, at a minimum, a graph, a weight map, and an output
- iterator. The edges of the MST (or MSF) will be output via the output
- iterator on process 0: other processes may receive edges on their
- output iterators, but the set may not be complete, depending on the
- algorithm. The algorithm parameters are documented together, because
- they do not vary greatly. See the section <a class="reference internal" href="#selecting-an-mst-algorithm">Selecting an MST
- algorithm</a> for advice on algorithm selection.</p>
- <p>The graph itself must model the <a class="reference external" href="http://www.boost.org/libs/graph/doc/VertexListGraph.html">Vertex List Graph</a> concept and the
- Distributed Edge List Graph concept. Since the most common
- distributed graph structure, the <a class="reference external" href="distributed_adjacency_list.html">distributed adjacency list</a>, only
- models the Distributed Vertex List Graph concept, it may only be used
- with these algorithms when wrapped in a suitable adaptor, such as the
- <a class="reference external" href="vertex_list_adaptor.html">vertex_list_adaptor</a>.</p>
- <div class="contents topic" id="contents">
- <p class="topic-title first">Contents</p>
- <ul class="simple">
- <li><a class="reference internal" href="#where-defined" id="id12">Where Defined</a></li>
- <li><a class="reference internal" href="#parameters" id="id13">Parameters</a></li>
- <li><a class="reference internal" href="#dense-boruvka-minimum-spanning-tree" id="id14"><tt class="docutils literal"><span class="pre">dense_boruvka_minimum_spanning_tree</span></tt></a><ul>
- <li><a class="reference internal" href="#description" id="id15">Description</a></li>
- <li><a class="reference internal" href="#complexity" id="id16">Complexity</a></li>
- <li><a class="reference internal" href="#performance" id="id17">Performance</a></li>
- </ul>
- </li>
- <li><a class="reference internal" href="#merge-local-minimum-spanning-trees" id="id18"><tt class="docutils literal"><span class="pre">merge_local_minimum_spanning_trees</span></tt></a><ul>
- <li><a class="reference internal" href="#id2" id="id19">Description</a></li>
- <li><a class="reference internal" href="#id3" id="id20">Complexity</a></li>
- <li><a class="reference internal" href="#id4" id="id21">Performance</a></li>
- </ul>
- </li>
- <li><a class="reference internal" href="#boruvka-then-merge" id="id22"><tt class="docutils literal"><span class="pre">boruvka_then_merge</span></tt></a><ul>
- <li><a class="reference internal" href="#id5" id="id23">Description</a></li>
- <li><a class="reference internal" href="#id6" id="id24">Complexity</a></li>
- <li><a class="reference internal" href="#id7" id="id25">Performance</a></li>
- </ul>
- </li>
- <li><a class="reference internal" href="#boruvka-mixed-merge" id="id26"><tt class="docutils literal"><span class="pre">boruvka_mixed_merge</span></tt></a><ul>
- <li><a class="reference internal" href="#id8" id="id27">Description</a></li>
- <li><a class="reference internal" href="#id9" id="id28">Complexity</a></li>
- <li><a class="reference internal" href="#id10" id="id29">Performance</a></li>
- </ul>
- </li>
- <li><a class="reference internal" href="#selecting-an-mst-algorithm" id="id30">Selecting an MST algorithm</a><ul>
- <li><a class="reference internal" href="#performance-on-sparse-graphs" id="id31">Performance on Sparse Graphs</a></li>
- <li><a class="reference internal" href="#performance-on-dense-graphs" id="id32">Performance on Dense Graphs</a></li>
- </ul>
- </li>
- </ul>
- </div>
- <div class="section" id="where-defined">
- <h1><a class="toc-backref" href="#id12">Where Defined</a></h1>
- <p><<tt class="docutils literal"><span class="pre">boost/graph/distributed/dehne_gotz_min_spanning_tree.hpp</span></tt>></p>
- </div>
- <div class="section" id="parameters">
- <h1><a class="toc-backref" href="#id13">Parameters</a></h1>
- <dl class="docutils">
- <dt>IN: <tt class="docutils literal"><span class="pre">Graph&</span> <span class="pre">g</span></tt></dt>
- <dd>The graph type must be a model of <a class="reference external" href="http://www.boost.org/libs/graph/doc/VertexListGraph.html">Vertex List Graph</a> and
- <a class="reference external" href="DistributedEdgeListGraph.html">Distributed Edge List Graph</a>.</dd>
- <dt>IN/OUT: <tt class="docutils literal"><span class="pre">WeightMap</span> <span class="pre">weight</span></tt></dt>
- <dd>The weight map must be a <a class="reference external" href="distributed_property_map.html">Distributed Property Map</a> and a <a class="reference external" href="http://www.boost.org/libs/property_map/ReadablePropertyMap.html">Readable
- Property Map</a> whose key type is the edge descriptor of the graph
- and whose value type is numerical.</dd>
- <dt>IN/OUT: <tt class="docutils literal"><span class="pre">OutputIterator</span> <span class="pre">out</span></tt></dt>
- <dd>The output iterator through which the edges of the MSF will be
- written. Must be capable of accepting edge descriptors for output.</dd>
- <dt>IN: <tt class="docutils literal"><span class="pre">VertexIndexMap</span> <span class="pre">index</span></tt></dt>
- <dd><p class="first">A mapping from vertex descriptors to indices in the range <em>[0,
- num_vertices(g))</em>. This must be a <a class="reference external" href="http://www.boost.org/libs/property_map/ReadablePropertyMap.html">Readable Property Map</a> whose
- key type is a vertex descriptor and whose value type is an integral
- type, typically the <tt class="docutils literal"><span class="pre">vertices_size_type</span></tt> of the graph.</p>
- <p class="last"><strong>Default:</strong> <tt class="docutils literal"><span class="pre">get(vertex_index,</span> <span class="pre">g)</span></tt></p>
- </dd>
- <dt>IN/UTIL: <tt class="docutils literal"><span class="pre">RankMap</span> <span class="pre">rank_map</span></tt></dt>
- <dd><p class="first">Stores the rank of each vertex, which is used for maintaining
- union-find data structures. This must be a <a class="reference external" href="http://www.boost.org/libs/property_map/ReadWritePropertyMap.html">Read/Write Property Map</a>
- whose key type is a vertex descriptor and whose value type is an
- integral type.</p>
- <p class="last"><strong>Default:</strong> An <tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> built from an STL vector
- of the <tt class="docutils literal"><span class="pre">vertices_size_type</span></tt> of the graph and the vertex index map.</p>
- </dd>
- <dt>IN/UTIL: <tt class="docutils literal"><span class="pre">ParentMap</span> <span class="pre">parent_map</span></tt></dt>
- <dd><p class="first">Stores the parent (representative) of each vertex, which is used for
- maintaining union-find data structures. This must be a <a class="reference external" href="http://www.boost.org/libs/property_map/ReadWritePropertyMap.html">Read/Write
- Property Map</a> whose key type is a vertex descriptor and whose value
- type is also a vertex descriptor.</p>
- <p class="last"><strong>Default:</strong> An <tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> built from an STL vector
- of the <tt class="docutils literal"><span class="pre">vertex_descriptor</span></tt> of the graph and the vertex index map.</p>
- </dd>
- <dt>IN/UTIL: <tt class="docutils literal"><span class="pre">SupervertexMap</span> <span class="pre">supervertex_map</span></tt></dt>
- <dd><p class="first">Stores the supervertex index of each vertex, which is used for
- maintaining the supervertex list data structures. This must be a
- <a class="reference external" href="http://www.boost.org/libs/property_map/ReadWritePropertyMap.html">Read/Write Property Map</a> whose key type is a vertex descriptor and
- whose value type is an integral type.</p>
- <p class="last"><strong>Default:</strong> An <tt class="docutils literal"><span class="pre">iterator_property_map</span></tt> built from an STL vector
- of the <tt class="docutils literal"><span class="pre">vertices_size_type</span></tt> of the graph and the vertex index map.</p>
- </dd>
- </dl>
- </div>
- <div class="section" id="dense-boruvka-minimum-spanning-tree">
- <h1><a class="toc-backref" href="#id14"><tt class="docutils literal"><span class="pre">dense_boruvka_minimum_spanning_tree</span></tt></a></h1>
- <pre class="literal-block">
- namespace graph {
- template<typename Graph, typename WeightMap, typename OutputIterator,
- typename VertexIndexMap, typename RankMap, typename ParentMap,
- typename SupervertexMap>
- OutputIterator
- dense_boruvka_minimum_spanning_tree(const Graph& g, WeightMap weight_map,
- OutputIterator out,
- VertexIndexMap index,
- RankMap rank_map, ParentMap parent_map,
- SupervertexMap supervertex_map);
- template<typename Graph, typename WeightMap, typename OutputIterator,
- typename VertexIndex>
- OutputIterator
- dense_boruvka_minimum_spanning_tree(const Graph& g, WeightMap weight_map,
- OutputIterator out, VertexIndex index);
- template<typename Graph, typename WeightMap, typename OutputIterator>
- OutputIterator
- dense_boruvka_minimum_spanning_tree(const Graph& g, WeightMap weight_map,
- OutputIterator out);
- }
- </pre>
- <div class="section" id="description">
- <h2><a class="toc-backref" href="#id15">Description</a></h2>
- <p>The dense Boruvka distributed minimum spanning tree algorithm is a
- direct parallelization of the sequential MST algorithm by
- Boruvka. The algorithm first creates a <em>supervertex</em> out of each
- vertex. Then, in each iteration, it finds the smallest-weight edge
- incident to each vertex, collapses supervertices along these edges,
- and removals all self loops. The only difference between the
- sequential and parallel algorithms is that the parallel algorithm
- performs an all-reduce operation so that all processes have the
- global minimum set of edges.</p>
- <p>Unlike the other three algorithms, this algorithm emits the complete
- list of edges in the minimum spanning forest via the output iterator
- on all processes. It may therefore be more useful than the others
- when parallelizing sequential BGL programs.</p>
- </div>
- <div class="section" id="complexity">
- <h2><a class="toc-backref" href="#id16">Complexity</a></h2>
- <p>The distributed algorithm requires <em>O(log n)</em> BSP supersteps, each of
- which requires <em>O(m/p + n)</em> time and <em>O(n)</em> communication per
- process.</p>
- </div>
- <div class="section" id="performance">
- <h2><a class="toc-backref" href="#id17">Performance</a></h2>
- <p>The following charts illustrate the performance of this algorithm on
- various random graphs. We see that the algorithm scales well up to 64
- or 128 processors, depending on the type of graph, for dense
- graphs. However, for sparse graphs performance tapers off as the
- number of processors surpases <em>m/n</em>, i.e., the average degree (which
- is 30 for this graph). This behavior is expected from the algorithm.</p>
- <img align="left" alt="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_5.png" class="align-left" src="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_5.png" />
- <img alt="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_5_speedup_1.png" src="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_5_speedup_1.png" />
- <img align="left" alt="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_5.png" class="align-left" src="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_5.png" />
- <img alt="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_5_speedup_1.png" src="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_5_speedup_1.png" />
- </div>
- </div>
- <div class="section" id="merge-local-minimum-spanning-trees">
- <h1><a class="toc-backref" href="#id18"><tt class="docutils literal"><span class="pre">merge_local_minimum_spanning_trees</span></tt></a></h1>
- <pre class="literal-block">
- namespace graph {
- template<typename Graph, typename WeightMap, typename OutputIterator,
- typename VertexIndexMap>
- OutputIterator
- merge_local_minimum_spanning_trees(const Graph& g, WeightMap weight,
- OutputIterator out,
- VertexIndexMap index);
- template<typename Graph, typename WeightMap, typename OutputIterator>
- inline OutputIterator
- merge_local_minimum_spanning_trees(const Graph& g, WeightMap weight,
- OutputIterator out);
- }
- </pre>
- <div class="section" id="id2">
- <h2><a class="toc-backref" href="#id19">Description</a></h2>
- <p>The merging local MSTs algorithm operates by computing minimum
- spanning forests from the edges stored on each process. Then the
- processes merge their edge lists along a tree. The child nodes cease
- participating in the computation, but the parent nodes recompute MSFs
- from the newly acquired edges. In the final round, the root of the
- tree computes the global MSFs, having received candidate edges from
- every other process via the tree.</p>
- </div>
- <div class="section" id="id3">
- <h2><a class="toc-backref" href="#id20">Complexity</a></h2>
- <p>This algorithm requires <em>O(log_D p)</em> BSP supersteps (where <em>D</em> is the
- number of children in the tree, and is currently fixed at 3). Each
- superstep requires <em>O((m/p) log (m/p) + n)</em> time and <em>O(m/p)</em>
- communication per process.</p>
- </div>
- <div class="section" id="id4">
- <h2><a class="toc-backref" href="#id21">Performance</a></h2>
- <p>The following charts illustrate the performance of this algorithm on
- various random graphs. The algorithm only scales well for very dense
- graphs, where most of the work is performed in the initial stage and
- there is very little work in the later stages.</p>
- <img align="left" alt="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_6.png" class="align-left" src="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_6.png" />
- <img alt="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_6_speedup_1.png" src="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_6_speedup_1.png" />
- <img align="left" alt="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_6.png" class="align-left" src="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_6.png" />
- <img alt="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_6_speedup_1.png" src="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_6_speedup_1.png" />
- </div>
- </div>
- <div class="section" id="boruvka-then-merge">
- <h1><a class="toc-backref" href="#id22"><tt class="docutils literal"><span class="pre">boruvka_then_merge</span></tt></a></h1>
- <pre class="literal-block">
- namespace graph {
- template<typename Graph, typename WeightMap, typename OutputIterator,
- typename VertexIndexMap, typename RankMap, typename ParentMap,
- typename SupervertexMap>
- OutputIterator
- boruvka_then_merge(const Graph& g, WeightMap weight, OutputIterator out,
- VertexIndexMap index, RankMap rank_map,
- ParentMap parent_map, SupervertexMap
- supervertex_map);
- template<typename Graph, typename WeightMap, typename OutputIterator,
- typename VertexIndexMap>
- inline OutputIterator
- boruvka_then_merge(const Graph& g, WeightMap weight, OutputIterator out,
- VertexIndexMap index);
- template<typename Graph, typename WeightMap, typename OutputIterator>
- inline OutputIterator
- boruvka_then_merge(const Graph& g, WeightMap weight, OutputIterator out);
- }
- </pre>
- <div class="section" id="id5">
- <h2><a class="toc-backref" href="#id23">Description</a></h2>
- <p>This algorithm applies both Boruvka steps and local MSF merging steps
- together to achieve better asymptotic performance than either
- algorithm alone. It first executes Boruvka steps until only <em>n/(log_d
- p)^2</em> supervertices remain, then completes the MSF computation by
- performing local MSF merging on the remaining edges and
- supervertices.</p>
- </div>
- <div class="section" id="id6">
- <h2><a class="toc-backref" href="#id24">Complexity</a></h2>
- <p>This algorithm requires <em>log_D p</em> + <em>log log_D p</em> BSP supersteps. The
- time required by each superstep depends on the type of superstep
- being performed; see the distributed Boruvka or merging local MSFS
- algorithms for details.</p>
- </div>
- <div class="section" id="id7">
- <h2><a class="toc-backref" href="#id25">Performance</a></h2>
- <p>The following charts illustrate the performance of this algorithm on
- various random graphs. We see that the algorithm scales well up to 64
- or 128 processors, depending on the type of graph, for dense
- graphs. However, for sparse graphs performance tapers off as the
- number of processors surpases <em>m/n</em>, i.e., the average degree (which
- is 30 for this graph). This behavior is expected from the algorithm.</p>
- <img align="left" alt="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_7.png" class="align-left" src="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_7.png" />
- <img alt="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_7_speedup_1.png" src="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_7_speedup_1.png" />
- <img align="left" alt="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_7.png" class="align-left" src="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_7.png" />
- <img alt="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_7_speedup_1.png" src="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_7_speedup_1.png" />
- </div>
- </div>
- <div class="section" id="boruvka-mixed-merge">
- <h1><a class="toc-backref" href="#id26"><tt class="docutils literal"><span class="pre">boruvka_mixed_merge</span></tt></a></h1>
- <pre class="literal-block">
- namespace {
- template<typename Graph, typename WeightMap, typename OutputIterator,
- typename VertexIndexMap, typename RankMap, typename ParentMap,
- typename SupervertexMap>
- OutputIterator
- boruvka_mixed_merge(const Graph& g, WeightMap weight, OutputIterator out,
- VertexIndexMap index, RankMap rank_map,
- ParentMap parent_map, SupervertexMap
- supervertex_map);
- template<typename Graph, typename WeightMap, typename OutputIterator,
- typename VertexIndexMap>
- inline OutputIterator
- boruvka_mixed_merge(const Graph& g, WeightMap weight, OutputIterator out,
- VertexIndexMap index);
- template<typename Graph, typename WeightMap, typename OutputIterator>
- inline OutputIterator
- boruvka_mixed_merge(const Graph& g, WeightMap weight, OutputIterator out);
- }
- </pre>
- <div class="section" id="id8">
- <h2><a class="toc-backref" href="#id27">Description</a></h2>
- <p>This algorithm applies both Boruvka steps and local MSF merging steps
- together to achieve better asymptotic performance than either method
- alone. In each iteration, the algorithm first performs a Boruvka step
- and then merges the local MSFs computed based on the supervertex
- graph.</p>
- </div>
- <div class="section" id="id9">
- <h2><a class="toc-backref" href="#id28">Complexity</a></h2>
- <p>This algorithm requires <em>log_D p</em> BSP supersteps. The
- time required by each superstep depends on the type of superstep
- being performed; see the distributed Boruvka or merging local MSFS
- algorithms for details. However, the algorithm is
- communication-optional (requiring <em>O(n)</em> communication overall) when
- the graph is sufficiently dense, i.e., <em>m/n >= p</em>.</p>
- </div>
- <div class="section" id="id10">
- <h2><a class="toc-backref" href="#id29">Performance</a></h2>
- <p>The following charts illustrate the performance of this algorithm on
- various random graphs. We see that the algorithm scales well up to 64
- or 128 processors, depending on the type of graph, for dense
- graphs. However, for sparse graphs performance tapers off as the
- number of processors surpases <em>m/n</em>, i.e., the average degree (which
- is 30 for this graph). This behavior is expected from the algorithm.</p>
- <img align="left" alt="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_8.png" class="align-left" src="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_8.png" />
- <img alt="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_8_speedup_1.png" src="chart_php_generator_ER_SF_SW_dataset_TimeSparse_columns_8_speedup_1.png" />
- <img align="left" alt="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_8.png" class="align-left" src="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_8.png" />
- <img alt="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_8_speedup_1.png" src="chart_php_generator_ER_SF_SW_dataset_TimeDense_columns_8_speedup_1.png" />
- </div>
- </div>
- <div class="section" id="selecting-an-mst-algorithm">
- <h1><a class="toc-backref" href="#id30">Selecting an MST algorithm</a></h1>
- <p>Dehne and Gotz reported <a class="citation-reference" href="#dg98" id="id11">[DG98]</a> mixed results when evaluating these
- four algorithms. No particular algorithm was clearly better than the
- others in all cases. However, the asymptotically best algorithm
- (<tt class="docutils literal"><span class="pre">boruvka_mixed_merge</span></tt>) seemed to perform more poorly in their tests
- than the other merging-based algorithms. The following performance
- charts illustrate the performance of these four minimum spanning tree
- implementations.</p>
- <p>Overall, <tt class="docutils literal"><span class="pre">dense_boruvka_minimum_spanning_tree</span></tt> gives the most
- consistent performance and scalability for the graphs we
- tested. Additionally, it may be more suitable for sequential programs
- that are being parallelized, because it emits complete MSF edge lists
- via the output iterators in every process.</p>
- <div class="section" id="performance-on-sparse-graphs">
- <h2><a class="toc-backref" href="#id31">Performance on Sparse Graphs</a></h2>
- <img align="left" alt="chart_php_generator_ER_dataset_TimeSparse_columns_5_6_7_8.png" class="align-left" src="chart_php_generator_ER_dataset_TimeSparse_columns_5_6_7_8.png" />
- <img alt="chart_php_generator_ER_dataset_TimeSparse_columns_5_6_7_8_speedup_1.png" src="chart_php_generator_ER_dataset_TimeSparse_columns_5_6_7_8_speedup_1.png" />
- <img align="left" alt="chart_php_generator_SF_dataset_TimeSparse_columns_5_6_7_8.png" class="align-left" src="chart_php_generator_SF_dataset_TimeSparse_columns_5_6_7_8.png" />
- <img alt="chart_php_generator_SF_dataset_TimeSparse_columns_5_6_7_8_speedup_1.png" src="chart_php_generator_SF_dataset_TimeSparse_columns_5_6_7_8_speedup_1.png" />
- <img align="left" alt="chart_php_generator_SW_dataset_TimeSparse_columns_5_6_7_8.png" class="align-left" src="chart_php_generator_SW_dataset_TimeSparse_columns_5_6_7_8.png" />
- <img alt="chart_php_generator_SW_dataset_TimeSparse_columns_5_6_7_8_speedup_1.png" src="chart_php_generator_SW_dataset_TimeSparse_columns_5_6_7_8_speedup_1.png" />
- </div>
- <div class="section" id="performance-on-dense-graphs">
- <h2><a class="toc-backref" href="#id32">Performance on Dense Graphs</a></h2>
- <img align="left" alt="chart_php_generator_ER_dataset_TimeDense_columns_5_6_7_8.png" class="align-left" src="chart_php_generator_ER_dataset_TimeDense_columns_5_6_7_8.png" />
- <img alt="chart_php_generator_ER_dataset_TimeDense_columns_5_6_7_8_speedup_1.png" src="chart_php_generator_ER_dataset_TimeDense_columns_5_6_7_8_speedup_1.png" />
- <img align="left" alt="chart_php_generator_SF_dataset_TimeDense_columns_5_6_7_8.png" class="align-left" src="chart_php_generator_SF_dataset_TimeDense_columns_5_6_7_8.png" />
- <img alt="chart_php_generator_SF_dataset_TimeDense_columns_5_6_7_8_speedup_1.png" src="chart_php_generator_SF_dataset_TimeDense_columns_5_6_7_8_speedup_1.png" />
- <img align="left" alt="chart_php_generator_SW_dataset_TimeDense_columns_5_6_7_8.png" class="align-left" src="chart_php_generator_SW_dataset_TimeDense_columns_5_6_7_8.png" />
- <img alt="chart_php_generator_SW_dataset_TimeDense_columns_5_6_7_8_speedup_1.png" src="chart_php_generator_SW_dataset_TimeDense_columns_5_6_7_8_speedup_1.png" />
- <hr class="docutils" />
- <p>Copyright (C) 2004 The Trustees of Indiana University.</p>
- <p>Authors: Douglas Gregor and Andrew Lumsdaine</p>
- <table class="docutils citation" frame="void" id="dg98" rules="none">
- <colgroup><col class="label" /><col /></colgroup>
- <tbody valign="top">
- <tr><td class="label">[DG98]</td><td><em>(<a class="fn-backref" href="#id1">1</a>, <a class="fn-backref" href="#id11">2</a>)</em> Frank Dehne and Silvia Gotz. <em>Practical Parallel Algorithms
- for Minimum Spanning Trees</em>. In Symposium on Reliable Distributed Systems,
- pages 366--371, 1998.</td></tr>
- </tbody>
- </table>
- </div>
- </div>
- </div>
- <div class="footer">
- <hr class="footer" />
- Generated on: 2009-05-31 00:21 UTC.
- Generated by <a class="reference external" href="http://docutils.sourceforge.net/">Docutils</a> from <a class="reference external" href="http://docutils.sourceforge.net/rst.html">reStructuredText</a> source.
- </div>
- </body>
- </html>
|