Concepedia

Path Compression

Path Compression is an optimization technique in the Disjoint Set Union data structure that, during a find operation, reconfigures the parent pointers of nodes along the search path to point directly to the root, thereby flattening the structure to improve future query efficiency.

33

Publications

1.7K

Citations

80

Authors

41

Institutions

Publications per year

2017–2026

5

Parents

Publications

33

Applications of Path Compression on Balanced Trees

Robert E. Tarjan · Journal of the ACM · 1979 · 300 citations · Full text

, , +6

Packet classification for core routers: is there an alternative to CAMs?

Florin Baboescu, Sumeet Singh, George Varghese · 2004 · 258 citations

, , +14

Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes

Haskell V. Hart · Medical Entomology and Zoology · 1986 · 184 citations

, , +8

A compression technique to materialize transitive closure

H. V. Jagadish · ACM Transactions on Database Systems · 1990 · 179 citations · Full text

, , +15

Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems

Adam L. Buchsbaum, Loukas Georgiadis, Haim Kaplan et al. · SIAM Journal on Computing · 2008 · 77 citations

, , +14

1–5 of 33

Authors

80

  1. RE
    Robert E. Tarjan

    Princeton University, United States

    4 publications · 406 citations

    4

    h-index

  2. AL
    Adam L. Buchsbaum

    AT&T (United States), United States

    3 publications · 158 citations

    3

    h-index

  3. AB
    Adi Botea

    IBM Research - Ireland, Ireland

    3 publications · 49 citations

    3

    h-index

  4. JW
    Jeffery Westbrook

    AT&T (United States), United States

    2 publications · 141 citations

    2

    h-index

  5. HV
    H. V. Jagadish

    AT&T (United States), United States

    2 publications · 191 citations

    2

    h-index

1–5 of 80

Institutions

41

  1. IBM Research - Ireland

    Dublin, Ireland

    3 h-index

    3 publications

    49 citations

  2. Stanford University

    Stanford, United States

    3 h-index

    3 publications

    326 citations

  3. AT&T (United States)

    Bedminster, United States

    3 h-index

    7 publications

    459 citations

  4. University of Southern California

    Los Angeles, United States

    2 h-index

    6 publications

    76 citations

  5. Data61

    Sydney, Australia

    2 h-index

    2 publications

    36 citations

  6. Tel Aviv University

    Tel Aviv, Israel

    1 h-index

    2 publications

    56 citations

  7. Indian Institute of Engineering Science and Technology, Shibpur

    Howrah, India

    1 h-index

    2 publications

    24 citations

  8. Ewha Womans University

    Seoul, South Korea

    1 h-index

    2 publications

    20 citations

1–8 of 41

Venues

  1. SIAM Journal on Computing

    4 publications · 145 citations

    4

    h-index

  2. ACM Transactions on Database Systems

    TODS · 2 publications · 234 citations

    2

    h-index

  3. 1

    h-index

  4. 1

    h-index

  5. 1

    h-index

1–5