loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
International Parallel and Distributed Processing Symposium (IPDPS'03)
The First Approximated Distributed Algorithm for the Minimum Degree Spanning Tree Problem on General Graphs
Nice, France
April 22-April 26
ISBN: 0-7695-1926-1
ASCII Text
x 
 
L. Blin, F. Butelle, "The First Approximated Distributed Algorithm for the Minimum Degree Spanning Tree Problem on General Graphs," Parallel and Distributed Processing Symposium, International, pp. 161a, International Parallel and Distributed Processing Symposium (IPDPS'03), 2003.
 
 
BibTex
x
 
@article{ 10.1109/IPDPS.2003.1213299,
author = {L. Blin and F. Butelle},
title = {The First Approximated Distributed Algorithm for the Minimum Degree Spanning Tree Problem on General Graphs},
journal ={Parallel and Distributed Processing Symposium, International},
volume = {0},
year = {2003},
issn = {1530-2075},
pages = {161a},
doi = {http://doi.ieeecomputersociety.org/10.1109/IPDPS.2003.1213299},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Parallel and Distributed Processing Symposium, International
TI - The First Approximated Distributed Algorithm for the Minimum Degree Spanning Tree Problem on General Graphs
SN - 1530-2075
SP
EP
A1 - L. Blin,
A1 - F. Butelle,
PY - 2003
KW - Distributed algorithms
KW - Spanning trees
KW - Minimum degree spanning trees
KW - Asynchronous algorithms
KW - general graphs
VL - 0
JA - Parallel and Distributed Processing Symposium, International
ER -
 
L. Blin, Université Paris-Nord
F. Butelle, Université Paris-Nord
In this paper we present the first distributed algorithm on general graphs for the Minimum Degree Spanning Tree problem. The problem is NP-hard in sequential. Our algorithm give a Spanning Tree of a degree at most 1 from the optimal. The resulting distributed algorithm is asynchronous, it works for named asynchronous arbitrary networks and achieves O(|V|) time complexity and O(|V| |E|) message complexity.
Index Terms:
Distributed algorithms, Spanning trees, Minimum degree spanning trees, Asynchronous algorithms, general graphs
Citation:
L. Blin, F. Butelle, "The First Approximated Distributed Algorithm for the Minimum Degree Spanning Tree Problem on General Graphs," ipdps, pp.161a, International Parallel and Distributed Processing Symposium (IPDPS'03), 2003
Usage of this product signifies your acceptance of the Terms of Use.