Concepedia

Tree Contraction

Tree Contraction is a parallel algorithmic technique in computational graph theory that repeatedly reduces the size of a tree by merging nodes and edges through a sequence of local operations, specifically aiming to simplify the tree structure while preserving essential connectivity and enabling efficient evaluation of tree-based computations.

47

Publications

2.3K

Citations

99

Authors

55

Institutions

Publications per year

2017–2026

3

Parents

Publications

47

Parallel tree contraction and its application

Gary L. Miller, John H. Reif · 1985 · 411 citations

, , +8

A simple parallel tree contraction algorithm

Karl Abrahamson, Norm Dadoun, David Kirkpatrick et al. · Journal of Algorithms · 1989 · 246 citations

, , +10

The contraction method for recursive algorithms

U. Rösler, Ludger Rüschendorf · Algorithmica · 2001 · 179 citations

, , +9

Parallel Tree Contraction Part 2: Further Applications

Gary L. Miller, John H. Reif · SIAM Journal on Computing · 1991 · 104 citations

, , +16

Highly scalable algorithms for rectilinear and octilinear Steiner trees

Andrew B. Kahng, Ion Măndoiu, Alex Zelikovsky · 2003 · 85 citations

, , +15

1–5 of 47

Authors

99

  1. GE
    Guy E. Blelloch

    Carnegie Mellon University, United States

    5 publications · 216 citations

    5

    h-index

  2. GL
    Gary L. Miller

    Carnegie Mellon University, United States

    3 publications · 583 citations

    3

    h-index

  3. JS
    Julian Shun

    Carnegie Mellon University, United States

    3 publications · 107 citations

    3

    h-index

  4. JH
    John H. Reif

    Duke University, United States

    3 publications · 583 citations

    3

    h-index

  5. LR
    Ludger Rüschendorf

    University of Freiburg, Germany

    3 publications · 216 citations

    3

    h-index

1–5 of 99

Institutions

55

  1. University of California San Diego

    San Diego, United States

    4 h-index

    6 publications

    300 citations

  2. Carnegie Mellon University

    Pittsburgh, United States

    4 h-index

    18 publications

    858 citations

  3. University of Bergen

    Bergen, Norway

    3 h-index

    5 publications

    222 citations

  4. Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier

    Montpellier, France

    2 h-index

    4 publications

    140 citations

  5. Université de Montpellier

    Montpellier, France

    2 h-index

    4 publications

    140 citations

  6. Stevens Institute of Technology

    Hoboken, United States

    2 h-index

    3 publications

    95 citations

  7. Princeton University

    Princeton, United States

    2 h-index

    4 publications

    124 citations

  8. University of British Columbia

    Vancouver, Canada

    2 h-index

    5 publications

    780 citations

1–8 of 55

Venues

  1. Algorithmica

    3 publications · 237 citations

    3

    h-index

  2. Journal of Algorithms

    2 publications · 258 citations

    2

    h-index

  3. Discrete Applied Mathematics

    2 publications · 55 citations

    2

    h-index

  4. 2

    h-index

  5. Journal of Combinatorial Theory Series B

    2 publications · 120 citations

    2

    h-index

1–5