On sparse graphs with dense long paths.

No abstract is available for this paper.

• Publication year

  1975

• Venue

  Computers & Mathematics With Applications

• Publication date

  1975-09-01

• Fields of study

  Mathematics

• Identifiers
  DOI 10.1016/0898-1221(75)90037-1
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• No references are available for this paper.

• Towards Practical Data-Dependent Memory-Hard Functions with Optimal Sustained Space Trade-offs in the Parallel Random Oracle Model

  2025cites this paper
• On Graphs of Incremental Proofs of Sequential Work

  2025influential citation
• Decentralized Data Archival: New Definitions and Constructions

  2025cites this paper
• SIGACT News Complexity Theory Column 126 Locally Decodable Codes for Insertions and Deletions

  2025influential citation
• Software-Based Memory Erasure with Relaxed Isolation Requirements

  2024cites this paper
• Proofs of Space with Maximal Hardness

  2024cites this paper
• Computationally Relaxed Locally Decodable Codes, Revisited

  2023cites this paper
• Sustained Space and Cumulative Complexity Trade-offs for Data-Dependent Memory-Hard Functions

  2022influential citation
• On Explicit Constructions of Extremely Depth Robust Graphs

  2021influential citation
• Parallel Quantum Pebbling: Analyzing the Post-Quantum Security of iMHFs

  2021cites this paper
• Rounds versus time for the two person pebble game

  2021cites this paper
• The Parallel Reversible Pebbling Game: Analyzing the Post-Quantum Security of iMHFs

  2021cites this paper
• Resisting newborn attacks via shared Proof-of-Space

  2021cites this paper
• Largest Component and Node Fault Tolerance for Grids

  2021cites this paper
• Memory-Hard Puzzles in the Standard Model with Applications to Memory-Hard Functions and Resource-Bounded Locally Decodable Codes

  2021cites this paper
• Locally Decodable/Correctable Codes for Insertions and Deletions

  2020cites this paper
• Vertex-Fault Tolerant Complete Matching in Bipartite graphs: the Biregular Case

  2019cites this paper
• A quadratic lower bound for algebraic branching programs

  2019influential citation
• Minimum k-critical bipartite graphs

  2019cites this paper
• Quadratic Lower Bounds for Algebraic Branching Programs and Formulas

  2019cites this paper
• A Synchronization-Avoiding Distance-1 Grundy Coloring Algorithm for Power-Law Graphs

  2019cites this paper
• Data structures meet cryptography: 3SUM with preprocessing

  2019cites this paper
• A New Connection Between Node and Edge Depth Robust Graphs

  2019cites this paper
• PIEs: Public Incompressible Encodings for Decentralized Storage

  2019cites this paper
• Tight Proofs of Space and Replication

  2019influential citation
• Relaxed Locally Correctable Codes in Computationally Bounded Channels*

  2019cites this paper
• Fe b 20 19 Static Data Structure Lower Bounds Imply Rigidity

  2019cites this paper
• On Explicit Depth Robust Graphs

  2019cites this paper
• Towards a Multi-Chain Future of Proof-of-Space

  2019cites this paper
• PoReps: Proofs of Space on Useful Data

  2018cites this paper
• Proofs of Catalytic Space

  2018cites this paper
• Simple Proofs of Sequential Work

  2018cites this paper
• Just In Time Hashing

  2018cites this paper
• Relaxed Locally Correctable Codes in Computationally Bounded Channels

  2018influential citation
• Static data structure lower bounds imply rigidity

  2018cites this paper
• Scaling Proof-of-Replication for Filecoin Mining

  2018cites this paper
• C C ] 1 2 N ov 2 01 8 Circuit Depth Reductions

  2018cites this paper
• Circuit Depth Reductions

  2018cites this paper
• Depth-Robust Graphs and Their Cumulative Memory Complexity

  2017cites this paper
• On the Depth-Robustness and Cumulative Pebbling Cost of Argon2i

  2017cites this paper
• Sustained Space Complexity

  2017cites this paper
• Practical Graphs for Optimal Side-Channel Resistant Memory-Hard Functions

  2017influential citation
• Cumulative Space in Black-White Pebbling and Resolution

  2017cites this paper
• Space in Proof Complexity

  2017cites this paper
• On the Computational Complexity of Minimal Cumulative Cost Graph Pebbling

  2016cites this paper
• Efficiently Computing Data-Independent Memory-Hard Functions

  2016cites this paper
• Proofs of Space

  2015influential citation
• High Parallel Complexity Graphs and Memory-Hard Functions

  2015cites this paper
• Reflections on Paul Erdős on His Birth Centenary, Part II

  2015cites this paper
• Complexity of Linear Boolean Operators

  2013cites this paper
• Expressing graph algorithms using generalized active messages

  2013cites this paper
• Complexity of Linear Boolean Operators Stasys Jukna

  2013cites this paper
• Active messages as a spanning model for parallel graph computation

  2013cites this paper
• Expressing graph algorithms using generalized active messages

  2013cites this paper
• Publicly verifiable proofs of sequential work

  2013cites this paper
• Eigenvalue asymptotics for Schrödinger operators on sparse graphs

  2013cites this paper
• Design of a Large-Scale Hybrid-Parallel Graph Library

  2010cites this paper
• Complexity Lower Bounds using Linear Algebra

  2009cites this paper
• GRAPH-THEORETIC ARGUMENTS IN LOW-LEVEL CONAOLEXITY

  2005cites this paper
• Communication Complexity of Simultaneous Messages

  2003cites this paper
• Optimal fault-tolerant linear arrays

  2003cites this paper
• Fault-Tolerant Meshes with Constant Degree

  2003cites this paper
• Fault-Tolerant Meshes with Small Degree

  2002cites this paper
• On separators, segregators and time versus space

  2001cites this paper
• Fault tolerant networks with small degree

  2000cites this paper
• Matrix Rigidity

  1999cites this paper
• Fault-Tolerant Networks for Parallel and VLSI Systems

  1998cites this paper
• Space Bounds for a Game on Graphs Space Bounds for a Game on Graphs F -e

  1998cites this paper
• How Good is Recursive Bisection?

  1997cites this paper
• Paul Erdös (1913-996): his influence on the theory of computing

  1997cites this paper
• One node fault tolerance for caterpillars and starlike trees

  1995cites this paper
• Shallow Grates

  1994cites this paper
• Rounds Versus Time for the Two Person Pebble Game

  1990cites this paper
• Rounds versus Time for the Two Person Pebble Game (Extended Abstract)

  1989cites this paper
• Figures of merit

  1989cites this paper
• Explicit construction of linear sized tolerant networks

  1988cites this paper
• Lower Bounds on Communication Overlap of Networks

  1986cites this paper
• Explicit expanders and the Ramanujan conjectures

  1986cites this paper
• Limitations on Explicit Constructions of Expanding Graphs

  1984cites this paper
• On determinism versus non-determinism and related problems

  1983cites this paper
• The Diogenes Approach to Testable Fault-Tolerant Arrays of Processors

  1983cites this paper
• On depth-reduction and grates

  1983cites this paper
• A Family of Graphs with Expensive Depth Reduction

  1981cites this paper
• Linear expected-time algorithms for connectivity problems (Extended Abstract)

  1980cites this paper
• Linear Expected-Time Algorithms for Connectivity Problems

  1980cites this paper
• Upper and lower bounds on time-space tradeoffs

  1979cites this paper
• On alternation

  1978cites this paper
• Graph-Theoretic Arguments in Low-Level Complexity

  1977influential citation
• Time-space trade-offs in a pebble game

  1977cites this paper
• Applications of a planar separator theorem

  1977cites this paper
• Generalized nested dissection

  1977cites this paper
• A Separator Theorem for Planar Graphs

  1977cites this paper
• Space Bounds for a Game of Graphs

  1976cites this paper
• Universal circuits (Preliminary Report)

  1976cites this paper
• Space bounds for a game on graphs

  1976cites this paper
• ANNALES DE L’INSTITUT FOURIER

  year unknowncites this paper