Concepedia

Pebbling Games

Pebbling Games is a theoretical framework in computational complexity that models the trade-offs between space and time resources by analyzing the minimum number of pebbles (representing memory) required to traverse a directed acyclic graph under specific placement and removal rules.

49

Publications

2.9K

Citations

83

Authors

48

Institutions

Publications per year

2017–2026

5

Parents

Publications

49

I/O complexity

Jiawei Hong, H. T. Kung · 1981 · 450 citations

, , +17

Coordinating Pebble Motion On Graphs, The Diameter Of Permutation Groups, And Applications

Daniel Kornhauser, Gary L. Miller, Paul G. Spirakis · 1984 · 285 citations · Full text

, , +11

Pebble game algorithms and sparse graphs

Audrey Lee, Ileana Streinu · Discrete Mathematics · 2007 · 223 citations

, , +14

Pebbling in Hypercubes

Fan Chung · SIAM Journal on Discrete Mathematics · 1989 · 181 citations

, , +15

A polynomial algorithm for the min-cut linear arrangement of trees

Mihalis Yannakakis · Journal of the ACM · 1985 · 127 citations · Full text

, , +10

1–5 of 49

Authors

83

  1. RE
    Robert E. Tarjan

    Princeton University, United States

    6 publications · 380 citations

    6

    h-index

  2. JN
    Jakob Nordstr”öm

    KTH Royal Institute of Technology, Sweden

    3 publications · 66 citations

    3

    h-index

  3. SM
    Siu Man Chan

    University of California, Berkeley, United States

    3 publications · 60 citations

    3

    h-index

  4. PH
    Philipp Hertel

    University of Toronto, Canada

    2 publications · 71 citations

    2

    h-index

  5. PG
    Phokion G. Kolaitis

    University of California, Santa Cruz, United States

    2 publications · 136 citations

    2

    h-index

1–5 of 83

Institutions

48

  1. Stanford University

    Stanford, United States

    5 h-index

    9 publications

    674 citations

  2. Bielefeld University

    Bielefeld, Germany

    3 h-index

    3 publications

    93 citations

  3. KTH Royal Institute of Technology

    Stockholm, Sweden

    3 h-index

    7 publications

    134 citations

  4. Smith College

    Northampton, United States

    2 h-index

    2 publications

    261 citations

  5. University of California, Santa Cruz

    Santa Cruz, United States

    2 h-index

    2 publications

    136 citations

  6. University of Massachusetts Amherst

    Amherst Center, United States

    2 h-index

    2 publications

    261 citations

  7. University of California, Berkeley

    Berkeley, United States

    2 h-index

    4 publications

    59 citations

  8. Université Grenoble Alpes

    Saint-Martin-d'Hères, France

    2 h-index

    4 publications

    147 citations

1–8 of 48

Venues

  1. SIAM Journal on Computing

    3 publications · 95 citations

    3

    h-index

  2. Journal of the ACM

    JACM · 3 publications · 239 citations

    3

    h-index

  3. Theoretical Computer Science

    2 publications · 65 citations

    2

    h-index

  4. Integers

    1 publications · 11 citations

    1

    h-index

  5. ArXiv.org

    Repository · 1 publications · 11 citations

    1

    h-index

1–5