ON THE EXPECTED PERFORMANCE OF PATH COMPRESSION ALGORITHMS.

Andrew C. Yao

doi:10.1137/0214010

ON THE EXPECTED PERFORMANCE OF PATH COMPRESSION ALGORITHMS.

Andrew C. Yao

Faculty of Electronic and Information Engineering

Research output: Contribution to journal › Article › peer-review

11 Scopus citations

Abstract

The author considers the expected running time of an equivalence algorithm using the path compression rule (but not the weighting rule). An O(n) expected running time is proved for the execution of a random equivalence program in the Spanning Tree Model.

Original language	English
Pages (from-to)	129-133
Number of pages	5
Journal	SIAM Journal on Computing
Volume	14
Issue number	1
DOIs	https://doi.org/10.1137/0214010
State	Published - 1985

Access to Document

10.1137/0214010

Cite this

@article{9a938205139f444cbd6aa040fcc6513b,

title = "ON THE EXPECTED PERFORMANCE OF PATH COMPRESSION ALGORITHMS.",

abstract = "The author considers the expected running time of an equivalence algorithm using the path compression rule (but not the weighting rule). An O(n) expected running time is proved for the execution of a random equivalence program in the Spanning Tree Model.",

author = "Yao, \{Andrew C.\}",

year = "1985",

doi = "10.1137/0214010",

language = "英语",

volume = "14",

pages = "129--133",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "1",

}

TY - JOUR

T1 - ON THE EXPECTED PERFORMANCE OF PATH COMPRESSION ALGORITHMS.

AU - Yao, Andrew C.

PY - 1985

Y1 - 1985

N2 - The author considers the expected running time of an equivalence algorithm using the path compression rule (but not the weighting rule). An O(n) expected running time is proved for the execution of a random equivalence program in the Spanning Tree Model.

AB - The author considers the expected running time of an equivalence algorithm using the path compression rule (but not the weighting rule). An O(n) expected running time is proved for the execution of a random equivalence program in the Spanning Tree Model.

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

U2 - 10.1137/0214010

DO - 10.1137/0214010

M3 - 文章

AN - SCOPUS:0022011082

SN - 0097-5397

VL - 14

SP - 129

EP - 133

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 1

ER -

ON THE EXPECTED PERFORMANCE OF PATH COMPRESSION ALGORITHMS.

Abstract

Access to Document

Other files and links

Fingerprint

Cite this