東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

New bounds in cell probe model.

Xiao, Bing.

Linked to FindBook

Google Book

Amazon

博客來

New bounds in cell probe model.

Record Type:	Electronic resources : Monograph/item
Title/Author:	New bounds in cell probe model./
Author:	Xiao, Bing.
Description:	68 p.
Notes:	Source: Dissertation Abstracts International, Volume: 53-03, Section: B, page: 1409.
Contained By:	Dissertation Abstracts International53-03B.
Subject:	Mathematics. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=9223350

New bounds in cell probe model.
Xiao, Bing.

New bounds in cell probe model. - 68 p.

Source: Dissertation Abstracts International, Volume: 53-03, Section: B, page: 1409.

Thesis (Ph.D.)--University of California, San Diego, 1992.

The static predecessor problem concerns the representation of a subset A of the universe Subjects--Topical Terms:

515831
Mathematics.

New bounds in cell probe model.
LDR:02627nmm 2200289 4500 001 1835206
005 20071204070250.5
008 130610s1992 eng d
035 $a (UMI)AAI9223350
035 $a AAI9223350
040 $a UMI $c UMI
100 1 $a Xiao, Bing. $3 1908219
245 1 0 $a New bounds in cell probe model.
300 $a 68 p.
500 $a Source: Dissertation Abstracts International, Volume: 53-03, Section: B, page: 1409.
500 $a Chair: Michael L. Fredman.
502 $a Thesis (Ph.D.)--University of California, San Diego, 1992.
520 $a The static predecessor problem concerns the representation of a subset A of the universe $ The operations supported are queries "find the largest element in A that is less than or equal to $i \in\ U $" . We extend results of M. Ajtai to show that any implementation of such a problem with space bounded by poly( $\ vert A\vert $) and poly( $\ log\ u $) word size requires $\ Omega({\log\ \log\ u\over\log\ \log\ \log\ u}) $ probes to answer a query in the worst case. The same lower bound is also proved for the dynamic predecessor problem in which the space restriction is dropped and the update operations are added.
520 $a The union-find problem is a problem of maintaining a collection of sets under the union and find operations. We generalize the union-find problem to a link-find problem with the unions being done by linking two vertices in a predefined graph. We extend results of R. Lipton and R. Tarjan to show that there exists a cell probe algorithm, in the amortized sense, achieving linear time complexity for the link-find problem if the underlying graphs satisfy some constrains. We then prove that the planar graphs satisfy such constrains and thus linear cell probe algorithms for the link-find problem can be implemented on them.
520 $a Another generalization of the union-find problem, called the union-find problem with backtracking, is defined by adding backtracking operations which undo the most recently performed union operation that has not yet been undone. We extend results of J. Westbrook and R. Tarjan to show that a worst case lower bound of $\ Omega({\log\ n\over\log\ \log\ n}) $ holds for the faithful cell probe algorithms solving the union-find problem with backtracking. We also present a faithful algorithm that solves the problem in time $ and space $.
590 $a School code: 0033.
650 4 $a Mathematics. $3 515831
650 4 $a Computer Science. $3 626642
690 $a 0405
690 $a 0984
710 2 0 $a University of California, San Diego. $3 1018093
773 0 $t Dissertation Abstracts International $g 53-03B.
790 1 0 $a Fredman, Michael L., $e advisor
790 $a 0033
791 $a Ph.D.
792 $a 1992
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=9223350