On the public citation graph

The Pebbling Problem is Complete in Polynomial Space

https://doi.org/10.1137/0209038

0 signed · 83 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.

Claim with ORCID

Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.

See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/3-540-08860-1_22openalex-snapshot

A pspace complete problem related to a pebble game

inferredcites →https://doi.org/10.1007/3-540-09118-1_12openalex-snapshot

Move rules and trade-offs in the pebble game

inferredcites →https://doi.org/10.1007/bf00289150openalex-snapshot

Time-space trade-offs in a pebble game

inferredcites →https://doi.org/10.1016/s0022-0000(70)80006-xopenalex-snapshot

Relationships between nondeterministic and deterministic tape complexities

inferredcites →https://doi.org/10.1109/sfcs.1978.17openalex-snapshot

GO is pspace hard

inferredcites →https://doi.org/10.1137/0204020openalex-snapshot

Complete Register Allocation Problems

inferredcites →https://doi.org/10.1145/321978.321989openalex-snapshot

A Combinatorial Problem Which Is Complete in Polynomial Space

inferredcites →https://doi.org/10.1145/322003.322015openalex-snapshot

On Time Versus Space

inferredcites →https://doi.org/10.1145/322077.322091openalex-snapshot

A Time-Space Trade-Off

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1007/3-540-10854-8_41openalex-snapshot

Pebbling and bandwidth

inferred← citeshttps://doi.org/10.1007/3-540-10856-4_75openalex-snapshot

Time and space bounded complexity classes and bandwidth constrained problems

inferred← citeshttps://doi.org/10.1007/3-540-16761-7_76openalex-snapshot

Min Cut is NP-complete for edge weighted trees

inferred← citeshttps://doi.org/10.1007/3-540-18625-5_44openalex-snapshot

Fast parallel algorithms for the subgraph homeomorphism and the subgraph isomorphism problem for classes of planar graphs

inferred← citeshttps://doi.org/10.1007/3-540-19488-6_130openalex-snapshot

A polynomial-time algorithm for subgraph isomorphism of two-connected series-parallel graphs

inferred← citeshttps://doi.org/10.1007/3-540-51498-8_45openalex-snapshot

On restricted Boolean circuits

inferred← citeshttps://doi.org/10.1007/3-540-54458-5_66openalex-snapshot

A new partition lemma for planar graphs and its application to circuit complexity

inferred← citeshttps://doi.org/10.1007/978-3-030-03807-6_2openalex-snapshot

Static-Memory-Hard Functions, and Modeling the Cost of Space vs. Time

inferred← citeshttps://doi.org/10.1007/978-3-031-52969-6_16openalex-snapshot

On the Target Pebbling Conjecture

inferred← citeshttps://doi.org/10.1007/978-3-319-08587-6_29openalex-snapshot

Skeptik: A Proof Compression System

inferred← citeshttps://doi.org/10.1007/978-3-319-21398-9_7openalex-snapshot

Reversible Pebble Game on Trees

inferred← citeshttps://doi.org/10.1007/978-3-540-74915-8_39openalex-snapshot

Game Characterizations and the PSPACE-Completeness of Tree Resolution Space

inferred← citeshttps://doi.org/10.1007/978-3-642-11512-7_2openalex-snapshot

Playing Savitch and Cooking Games

inferred← citeshttps://doi.org/10.1007/978-3-662-58387-6_18openalex-snapshot

On the Computational Complexity of Minimal Cumulative Cost Graph Pebbling

inferred← citeshttps://doi.org/10.1007/978-94-017-2740-2_17openalex-snapshot

Games, Complexity and Interaction the Role of Games in Computer Science

inferred← citeshttps://doi.org/10.1007/bf00264496openalex-snapshot

Black-white pebbles and graph separation

inferred← citeshttps://doi.org/10.1007/bf01756027openalex-snapshot

Single-suit two-person card play

inferred← citeshttps://doi.org/10.1007/bf02259908openalex-snapshot

Bandwidth and pebbling

inferred← citeshttps://doi.org/10.1007/s00037-020-00201-yopenalex-snapshot

Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling

inferred← citeshttps://doi.org/10.1007/s10009-017-0459-0openalex-snapshot

Greedy pebbling for proof space compression

inferred← citeshttps://doi.org/10.1007/s10766-014-0338-1openalex-snapshot

List Scheduling in Embedded Systems Under Memory Constraints

inferred← citeshttps://doi.org/10.1016/0020-0190(80)90136-2openalex-snapshot

The space complexity of pebble games on trees

inferred← citeshttps://doi.org/10.1016/0196-6774(83)90019-6openalex-snapshot

The NP-completeness column: An ongoing guide

inferred← citeshttps://doi.org/10.1016/0196-6774(86)90020-9openalex-snapshot

The NP-completeness column: An ongoing guide

inferred← citeshttps://doi.org/10.1016/0303-2647(86)90021-3openalex-snapshot

Sex and computing

inferred← citeshttps://doi.org/10.1016/0304-3975(82)90015-9openalex-snapshot

Pebble games for studying storage sharing

inferred← citeshttps://doi.org/10.1016/0304-3975(88)90028-xopenalex-snapshot

Min cut is NP-complete for edge weighted trees

inferred← citeshttps://doi.org/10.1016/0304-3975(89)90011-xopenalex-snapshot

Subgraph isomorphism for biconnected outerplanar graphs in cubic time

inferred← citeshttps://doi.org/10.1016/0304-3975(89)90127-8openalex-snapshot

On parallel complexity of the subgraph homeomorphism and the subgraph isomorphism problem for classes of planar graphs

inferred← citeshttps://doi.org/10.1016/0890-5401(91)90010-yopenalex-snapshot

Two dynamic programming algorithms for which interpreted pebbling helps

inferred← citeshttps://doi.org/10.1016/b978-0-444-88071-0.50006-0openalex-snapshot

Machine Models and Simulations

inferred← citeshttps://doi.org/10.1016/b978-0-444-88071-0.50007-2openalex-snapshot

A Catalog of Complexity Classes

inferred← citeshttps://doi.org/10.1016/j.ipl.2018.03.001openalex-snapshot

Cliques enumeration and tree-like resolution proofs

inferred← citeshttps://doi.org/10.1016/j.ipl.2018.04.007openalex-snapshot

On semantic cutting planes with very small coefficients

inferred← citeshttps://doi.org/10.1016/j.ipl.2018.04.014openalex-snapshot

A note about k -DNF resolution

inferred← citeshttps://doi.org/10.1016/j.ipl.2026.106637openalex-snapshot

I/O complexity and pebble games with partial computations

inferred← citeshttps://doi.org/10.1016/j.jcss.2017.07.009openalex-snapshot

Pebbling meets coloring: Reversible pebble game on trees

inferred← citeshttps://doi.org/10.1016/j.jda.2008.09.008openalex-snapshot

DAG reversal is NP-complete

inferred← citeshttps://doi.org/10.1016/j.jpdc.2014.10.004openalex-snapshot

Memory-aware tree traversals with pre-assigned tasks

inferred← citeshttps://doi.org/10.1016/j.jpdc.2019.01.009openalex-snapshot

Limiting the memory footprint when dynamically scheduling DAGs on shared-memory platforms

inferred← citeshttps://doi.org/10.1016/j.tcs.2002.11.001openalex-snapshot

Complexity, appeal and challenges of combinatorial games

inferred← citeshttps://doi.org/10.1016/j.tcs.2017.09.037openalex-snapshot

Scheduling series-parallel task graphs to minimize peak memory

inferred← citeshttps://doi.org/10.1016/s0304-3975(01)00179-7openalex-snapshot

Endgame problems of Sim-like graph Ramsey avoidance games are PSPACE-complete

inferred← citeshttps://doi.org/10.1017/9781316135167.033openalex-snapshot

Combinatorial Games: Selected Bibliography With A Succinct Gourmet Introduction

inferred← citeshttps://doi.org/10.1109/ccc.2010.22openalex-snapshot

On the Relative Strength of Pebbling and Resolution

inferred← citeshttps://doi.org/10.1109/focs.2007.22openalex-snapshot

Exponential Time/Space Speedups for Resolution and the PSPACE-completeness of Black-White Pebbling

inferred← citeshttps://doi.org/10.1109/focs.2007.25openalex-snapshot

Hardness Amplification for Errorless Heuristics

inferred← citeshttps://doi.org/10.1109/focs.2015.36openalex-snapshot

Hardness of Approximation in PSPACE and Separation Results for Pebble Games

inferred← citeshttps://doi.org/10.1109/ipdps.2011.60openalex-snapshot

On Optimal Tree Traversals for Sparse Matrix Factorization

inferred← citeshttps://doi.org/10.1109/ipdps.2013.55openalex-snapshot

Scheduling Tree-Shaped Task Graphs to Minimize Memory and Makespan

inferred← citeshttps://doi.org/10.1109/ipdpsw50202.2020.00102openalex-snapshot

Revisiting dynamic DAG scheduling under memory constraints for shared-memory platforms

inferred← citeshttps://doi.org/10.1109/sbac-pad.2013.22openalex-snapshot

List Scheduling in Embedded Systems under Memory Constraints

inferred← citeshttps://doi.org/10.1109/tassp.1984.1164433openalex-snapshot

Some complexity issues in digital signal processing

inferred← citeshttps://doi.org/10.1137/0608031openalex-snapshot

An Application of Generalized Tree Pebbling to Sparse Matrix Factorization

inferred← citeshttps://doi.org/10.1137/080713513openalex-snapshot

The PSPACE-Completeness of Black-White Pebbling

inferred← citeshttps://doi.org/10.1137/130914607openalex-snapshot

Pebbling in Split Graphs

inferred← citeshttps://doi.org/10.1142/9789812778031_0015openalex-snapshot

COMPLEXITY ISSUES IN DYNAMIC GEOMETRY

inferred← citeshttps://doi.org/10.1145/1374376.1374478openalex-snapshot

Towards an optimal separation of space and length in resolution

inferred← citeshttps://doi.org/10.1145/2159531.2159538openalex-snapshot

On the Relative Strength of Pebbling and Resolution

inferred← citeshttps://doi.org/10.1145/2779052openalex-snapshot

Parallel Scheduling of Task Trees with Limited Memory

inferred← citeshttps://doi.org/10.1145/3210377.3210387openalex-snapshot

Red-Blue Pebble Game

inferred← citeshttps://doi.org/10.1145/322344.322354openalex-snapshot

Asymptotically tight bounds on time-space trade-offs in a pebble game

inferred← citeshttps://doi.org/10.1145/4221.4228openalex-snapshot

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

inferred← citeshttps://doi.org/10.1145/800076.802474openalex-snapshot

Bandwidth constrained NP-Complete problems

inferred← citeshttps://doi.org/10.1201/9780429171529-59openalex-snapshot

Scheduling for Large-Scale Systems

inferred← citeshttps://doi.org/10.1201/b16132-83openalex-snapshot

Graph Pebbling

inferred← citeshttps://doi.org/10.15803/ijnc.11.1_27openalex-snapshot

Dynamic DAG Scheduling Under Memory Constraints for Shared-Memory Platforms

inferred← citeshttps://doi.org/10.3233/sat190066openalex-snapshot

Algorithms and Complexity Results for Input and Unit Resolution

inferred← citeshttps://doi.org/10.4086/toc.2013.v009a014openalex-snapshot

inferred← citeshttps://doi.org/10.4230/dagsemproc.08381.6openalex-snapshot

Understanding space in resolution: optimal lower bounds and exponential trade-offs

inferred← citeshttps://doi.org/10.48550/arxiv.1211.4049openalex-snapshot

Pebbling in Split Graphs

inferred← citeshttps://doi.org/10.48550/arxiv.1908.09606openalex-snapshot

Red-blue pebbling revisited: near optimal parallel matrix-matrix multiplication

inferred← citeshttps://doi.org/10.70675/29c38ac9z6d86z424dz8dcez148daedf433bopenalex-snapshot

Memory-aware Algorithms and Scheduling Techniques for Matrix Computattions

inferred← citeshttps://doi.org/10.70675/3f0c5b2cz09e4z450fzb2d7z6fe013164207openalex-snapshot

Memory-aware algorithms : from multicores to large scale platforms

Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.