Finding the shortest bottleneck edge in a parametric minimum spanning tree

Research output: Contribution to conferencePaperpeer-review

Abstract

The use of an randomized technique method to find the shortest bottleneck edge in a parametric minimum spanning tree is described. A constant number of subproblems is to be formed for applying the method, each of a fraction of the original size, such that the orginal problem can be expresses as the minimum of the answers to the subproblems. A simpler O(logn) method for off-line dynamic connectivity can also be obtained directly by divide-and- conquer over the update sequence. The results show that the decision problem can be solved in O(mlogn) time, and by the randomized reduction technique, the optimization problem can be solved in O(mlogn) expected time.

Original languageEnglish (US)
Pages917-918
Number of pages2
StatePublished - 2005
Externally publishedYes
EventSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States
Duration: Jan 23 2005Jan 25 2005

Other

OtherSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CityVancouver, BC
Period1/23/051/25/05

ASJC Scopus subject areas

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'Finding the shortest bottleneck edge in a parametric minimum spanning tree'. Together they form a unique fingerprint.

Cite this