Two dynamic programming algorithms for which interpreted pebbling helps

DOI10.1016/0890-5401(91)90010-YzbMath0725.90101MaRDI QIDQ2277375

H. Venkateswaran

Publication date: 1991

Published in: Information and Computation (Search for Journal in Brave)

zbMATH Keywords

pebble gamescontext-free language recognitiontransitive closure of directed graphs

Mathematics Subject Classification ID

2-person games (91A05) Games involving graphs (91A43) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Related Items (1)

The complexity of computing maximal word functions

Cites Work

• Speedups of deterministic machines by synchronous parallel machines
• Tree-size bounded alternation
• Properties that characterize LOGCFL
• An observation on time-storage trade off
• Fast Parallel Computation of Polynomials Using Few Processors
• A New Pebble Game that Characterizes Parallel Complexity Classes
• The Pebbling Problem is Complete in Polynomial Space
• Two Familiar Transitive Closure Algorithms Which Admit No Polynomial Time, Sublinear Space Implementations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Two dynamic programming algorithms for which interpreted pebbling helps