loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
13th International Conference on Parallel and Distributed Systems - Volume 1 (ICPADS'07)
Parallel Minimum Spanning Tree Heuristic for the steiner problem in graphs
Hsinchu, Taiwan
December 05-December 07
ISBN: 978-1-4244-1889-3
ASCII Text
x 
 
null Hoda Akbari, null Zeinab Iranmanesh, null Mohammad Ghodsi, "Parallel Minimum Spanning Tree Heuristic for the steiner problem in graphs," Parallel and Distributed Systems, International Conference on, vol. 1, pp. 1-8, 13th International Conference on Parallel and Distributed Systems - Volume 1 (ICPADS'07), 2007.
 
 
BibTex
x
 
@article{ 10.1109/ICPADS.2007.4447726,
author = {null Hoda Akbari and null Zeinab Iranmanesh and null Mohammad Ghodsi},
title = {Parallel Minimum Spanning Tree Heuristic for the steiner problem in graphs},
journal ={Parallel and Distributed Systems, International Conference on},
volume = {1},
year = {2007},
isbn = {978-1-4244-1889-3},
pages = {1-8},
doi = {http://doi.ieeecomputersociety.org/10.1109/ICPADS.2007.4447726},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Parallel and Distributed Systems, International Conference on
TI - Parallel Minimum Spanning Tree Heuristic for the steiner problem in graphs
SN - 978-1-4244-1889-3
SP1
EP8
A1 - null Hoda Akbari,
A1 - null Zeinab Iranmanesh,
A1 - null Mohammad Ghodsi,
PY - 2007
KW - null
VL - 1
JA - Parallel and Distributed Systems, International Conference on
ER -
 
null Hoda Akbari, Sharif University of Technology, Tehran, Iran
null Zeinab Iranmanesh, Sharif University of Technology, Tehran, Iran
null Mohammad Ghodsi, Sharif University of Technology, Tehran, Iran
Given an undirected graph with weights associated with its edges, the Steiner tree problem consists of finding a minimum weight subtree spanning a given subset of (terminal) nodes of the original graph. Minimum Spanning Tree Heuristic (MSTH) is a heuristic for solving the Steiner problem in graphs. In this paper we first review existing algorithms for solving the Steiner problem in graphs. We then introduce a new parallel version of MSTH on three dimensional mesh of trees architecture. We describe our algorithm and analyze its time complexity. The time complexity analysis shows that the algorithm’s running time is O(lg2 n) which is comparable with other existing parallel solutions.
Citation:
null Hoda Akbari, null Zeinab Iranmanesh, null Mohammad Ghodsi, "Parallel Minimum Spanning Tree Heuristic for the steiner problem in graphs," icpads, vol. 1, pp.1-8, 13th International Conference on Parallel and Distributed Systems - Volume 1 (ICPADS'07), 2007
Usage of this product signifies your acceptance of the Terms of Use.