語系:
繁體中文
English
說明(常見問題)
回圖書館首頁
手機版館藏查詢
登入
回首頁
切換:
標籤
|
MARC模式
|
ISBD
New bounds in cell probe model.
~
Xiao, Bing.
FindBook
Google Book
Amazon
博客來
New bounds in cell probe model.
紀錄類型:
書目-電子資源 : Monograph/item
正題名/作者:
New bounds in cell probe model./
作者:
Xiao, Bing.
面頁冊數:
68 p.
附註:
Source: Dissertation Abstracts International, Volume: 53-03, Section: B, page: 1409.
Contained By:
Dissertation Abstracts International53-03B.
標題:
Mathematics. -
電子資源:
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
筆 0 讀者評論
館藏地:
全部
電子資源
出版年:
卷號:
館藏
1 筆 • 頁數 1 •
1
條碼號
典藏地名稱
館藏流通類別
資料類型
索書號
使用類型
借閱狀態
預約狀態
備註欄
附件
W9226226
電子資源
11.線上閱覽_V
電子書
EB
一般使用(Normal)
在架
0
1 筆 • 頁數 1 •
1
多媒體
評論
新增評論
分享你的心得
Export
取書館
處理中
...
變更密碼
登入