NDLI: A fast distributed approximation algorithm for minimum spanning trees

Content Provider	Springer Nature Link
Author	Khan, Maleq Pandurangan, Gopal
Copyright Year	2007
Abstract	We present a distributed algorithm that constructs an O(log n)-approximate minimum spanning tree (MST) in any arbitrary network. This algorithm runs in time Õ(D(G) + L(G, w)) where L(G, w) is a parameter called the local shortest path diameter and D(G) is the (unweighted) diameter of the graph. Our algorithm is existentially optimal (up to polylogarithmic factors), i.e., there exist graphs which need Ω(D(G) + L(G, w)) time to compute an H-approximation to the MST for any $$H\,\in\,[1, \Theta({\rm log} n)]$$ . Our result also shows that there can be a significant time gap between exact and approximate MST computation: there exists graphs in which the running time of our approximation algorithm is exponentially faster than the time-optimal distributed algorithm that computes the MST. Finally, we show that our algorithm can be used to find an approximate MST in wireless networks and in random weighted networks in almost optimal Õ(D(G)) time.
Starting Page	391
Ending Page	402
Page Count	12
File Format	PDF
ISSN	01782770
Journal	Distributed Computing
Volume Number	20
Issue Number	6
e-ISSN	14320452
Language	English
Publisher	Springer-Verlag
Publisher Date	2007-10-30
Publisher Place	Berlin/Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Minimum spanning tree Distributed approximation algorithm Randomized algorithm Theory of Computation Software Engineering/Programming and Operating Systems Computer Systems Organization and Communication Networks Computer Hardware Computer Communication Networks
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science Computer Networks and Communications Computational Theory and Mathematics Hardware and Architecture

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Distributed verification of minimum spanning trees

Distributed MST for constant diameter graphs

Fast and compact self-stabilizing verification, computation, and fault detection of an MST

Efficient distributed approximation algorithms via probabilistic tree embeddings

An optimal bit complexity randomized distributed MIS algorithm

Randomized distributed decision

A local approximation algorithm for minimum dominating set problem in anonymous planar networks

Constant-time distributed dominating set approximation

Efficient distributed computation of distance sketches in networks

A fast distributed approximation algorithm for minimum spanning trees

Similar Documents

Distributed verification of minimum spanning trees

Distributed MST for constant diameter graphs

Fast and compact self-stabilizing verification, computation, and fault detection of an MST

Efficient distributed approximation algorithms via probabilistic tree embeddings

An optimal bit complexity randomized distributed MIS algorithm

Randomized distributed decision

A local approximation algorithm for minimum dominating set problem in anonymous planar networks

Constant-time distributed dominating set approximation

Efficient distributed computation of distance sketches in networks

A fast distributed approximation algorithm for minimum spanning trees