Optimal Parallel Verification of Minimum Spanning Trees in Logarithmic Time

B. Dixon; R. E. Tarjan

doi:10.1007/BF02523235

Optimal Parallel Verification of Minimum Spanning Trees in Logarithmic Time

B. Dixon, R. E. Tarjan

Research output: Contribution to journal › Article › peer-review

13 Scopus citations

Abstract

We present the first optimal parallel algorithms for the verification and sensitivity analysis of minimum spanning trees. Our algorithms are deterministic and run in O(log n) time and require linear-work in the CREW PRAM model. These algorithms are used as a subroutine in the linear-work randomized algorithm for finding minimum spanning trees of Cole, Klein, and Tarjan.

Original language	English (US)
Pages (from-to)	11-18
Number of pages	8
Journal	Algorithmica (New York)
Volume	17
Issue number	1
DOIs	https://doi.org/10.1007/BF02523235
State	Published - Jan 1997

All Science Journal Classification (ASJC) codes

General Computer Science
Computer Science Applications
Applied Mathematics

Keywords

Minimum spanning tree
Network optimization
Sensitivity analysis
Verification algorithms

Access to Document

10.1007/BF02523235

Cite this

@article{ea35beed927049e6bd663594330593e4,

title = "Optimal Parallel Verification of Minimum Spanning Trees in Logarithmic Time",

abstract = "We present the first optimal parallel algorithms for the verification and sensitivity analysis of minimum spanning trees. Our algorithms are deterministic and run in O(log n) time and require linear-work in the CREW PRAM model. These algorithms are used as a subroutine in the linear-work randomized algorithm for finding minimum spanning trees of Cole, Klein, and Tarjan.",

keywords = "Minimum spanning tree, Network optimization, Sensitivity analysis, Verification algorithms",

author = "B. Dixon and Tarjan, {R. E.}",

year = "1997",

month = jan,

doi = "10.1007/BF02523235",

language = "English (US)",

volume = "17",

pages = "11--18",

journal = "Algorithmica (New York)",

issn = "0178-4617",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - Optimal Parallel Verification of Minimum Spanning Trees in Logarithmic Time

AU - Dixon, B.

AU - Tarjan, R. E.

PY - 1997/1

Y1 - 1997/1

N2 - We present the first optimal parallel algorithms for the verification and sensitivity analysis of minimum spanning trees. Our algorithms are deterministic and run in O(log n) time and require linear-work in the CREW PRAM model. These algorithms are used as a subroutine in the linear-work randomized algorithm for finding minimum spanning trees of Cole, Klein, and Tarjan.

AB - We present the first optimal parallel algorithms for the verification and sensitivity analysis of minimum spanning trees. Our algorithms are deterministic and run in O(log n) time and require linear-work in the CREW PRAM model. These algorithms are used as a subroutine in the linear-work randomized algorithm for finding minimum spanning trees of Cole, Klein, and Tarjan.

KW - Minimum spanning tree

KW - Network optimization

KW - Sensitivity analysis

KW - Verification algorithms

UR - http://www.scopus.com/inward/record.url?scp=0008873343&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0008873343&partnerID=8YFLogxK

U2 - 10.1007/BF02523235

DO - 10.1007/BF02523235

M3 - Article

AN - SCOPUS:0008873343

SN - 0178-4617

VL - 17

SP - 11

EP - 18

JO - Algorithmica (New York)

JF - Algorithmica (New York)

IS - 1

ER -

Optimal Parallel Verification of Minimum Spanning Trees in Logarithmic Time

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this