On the average behavior of set merging algorithms (extended abstract)

Andrew Chi Ehih Yao

doi:10.1145/800113.803648

On the average behavior of set merging algorithms (extended abstract)

Andrew Chi Ehih Yao

电子与信息学部

科研成果: 期刊稿件 › 会议文章 › 同行评审

25 引用（Scopus）

摘要

In this paper we study the expected running tlme of a variety of algorithms that perform set merging. The set merging problem (for example, see AHU [13) is concerned with using suitable data structures to represent partition of a set S = { 1,2 .... ,n) so that a sequence of instructions of the form "x = y", meaning "Find the subset containing x; Find the subset containing y; Merge the two subsets if they are different.

源语言	英语
页（从-至）	192-195
页数	4
期刊	Proceedings of the Annual ACM Symposium on Theory of Computing
卷	Part F130841
DOI	https://doi.org/10.1145/800113.803648
出版状态	已出版 - 3 5月 1976
活动	8th Annual ACM Symposium on Theory of Computing, STOC 1976 - Hershey, 美国期限: 3 5月 1976 → 5 5月 1976

访问文件

10.1145/800113.803648

其它文件与链接

链接到 Scopus 的出版物

引用此

@article{7df7031dbf9d4e93b377b3baca573591,

title = "On the average behavior of set merging algorithms (extended abstract)",

abstract = "In this paper we study the expected running tlme of a variety of algorithms that perform set merging. The set merging problem (for example, see AHU [13) is concerned with using suitable data structures to represent partition of a set S = \{ 1,2 .... ,n) so that a sequence of instructions of the form {"}x = y{"}, meaning {"}Find the subset containing x; Find the subset containing y; Merge the two subsets if they are different.",

author = "Yao, \{Andrew Chi Ehih\}",

year = "1976",

month = may,

day = "3",

doi = "10.1145/800113.803648",

language = "英语",

volume = "Part F130841",

pages = "192--195",

journal = "Proceedings of the Annual ACM Symposium on Theory of Computing",

issn = "0737-8017",

publisher = "Association for Computing Machinery ",

note = "8th Annual ACM Symposium on Theory of Computing, STOC 1976 ; Conference date: 03-05-1976 Through 05-05-1976",

}

TY - JOUR

T1 - On the average behavior of set merging algorithms (extended abstract)

AU - Yao, Andrew Chi Ehih

PY - 1976/5/3

Y1 - 1976/5/3

N2 - In this paper we study the expected running tlme of a variety of algorithms that perform set merging. The set merging problem (for example, see AHU [13) is concerned with using suitable data structures to represent partition of a set S = { 1,2 .... ,n) so that a sequence of instructions of the form "x = y", meaning "Find the subset containing x; Find the subset containing y; Merge the two subsets if they are different.

AB - In this paper we study the expected running tlme of a variety of algorithms that perform set merging. The set merging problem (for example, see AHU [13) is concerned with using suitable data structures to represent partition of a set S = { 1,2 .... ,n) so that a sequence of instructions of the form "x = y", meaning "Find the subset containing x; Find the subset containing y; Merge the two subsets if they are different.

UR - https://www.scopus.com/pages/publications/84990734700

U2 - 10.1145/800113.803648

DO - 10.1145/800113.803648

M3 - 会议文章

AN - SCOPUS:84990734700

SN - 0737-8017

VL - Part F130841

SP - 192

EP - 195

JO - Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Proceedings of the Annual ACM Symposium on Theory of Computing

T2 - 8th Annual ACM Symposium on Theory of Computing, STOC 1976

Y2 - 3 May 1976 through 5 May 1976

ER -

On the average behavior of set merging algorithms (extended abstract)

摘要

访问文件

其它文件与链接

学术指纹

引用此