| | |
| | |
Stat |
Members: 3643 Articles: 2'487'895 Articles rated: 2609
28 March 2024 |
|
| | | |
|
Article overview
| |
|
Linear-Time Pointer-Machine Algorithms for Least Common Ancestors, MST Verification, and Dominators | Adam L. Buchsbaum
; Haim Kaplan
; Anne Rogers
; Jeffery R. Westbrook
; | Date: |
15 Jul 2002 | Subject: | Data Structures and Algorithms ACM-class: D.3.4; E.1; F.1.1; F.2.2; G.2.2 | cs.DS | Abstract: | We present two new data structure tools--disjoint set union with bottom-up linking, and pointer-based radix sort--and combine them with bottom-level microtrees to devise the first linear-time, pointer-machine algorithms for off-line least common ancestors, minimum spanning tree verification, and computing dominators in a flowgraph. Our results also imply the first randomized, linear-time algorithm for computing minimum spanning trees on a pointer machine. Specifically, we show that a sequence of $n-1$ unions and $m$ finds where the unions always include one of $ell$ designated special elements takes $O(malpha(m,ell)+n)$ time on a pointer machine. This result applies in particular to union trees on $ell$ leaves with a bottom-up union pattern. When $ell$ is slightly sublinear in $m$, the time bound becomes linear. We also show that for any tractable graph problem (generally restricted to consider only the topology of the input graph), a set of instances of total size $N$ can be solved on a pointer machine in O(N) time, as long as each instance is small with respect to $N$ (e.g., $O(log^{1/3} N)$ vertices each). We state these results generally and use them in turn-key fashion. | Source: | arXiv, cs.DS/0207061 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |