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 language | English (US) |
---|---|
Pages | 917-918 |
Number of pages | 2 |
State | Published - 2005 |
Externally published | Yes |
Event | Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States Duration: Jan 23 2005 → Jan 25 2005 |
Other
Other | Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|
Country/Territory | United States |
City | Vancouver, BC |
Period | 1/23/05 → 1/25/05 |
ASJC Scopus subject areas
- Software
- General Mathematics