Two dynamic programming algorithms for which interpreted pebbling helps

DOI10.1016/0890-5401(91)90010-YzbMATHMaRDI QIDQ2277375FDO

Authors 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

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

Recommendations

• scientific article; zbMATH DE number 3871062
• Pebbling Algorithms in Diameter Two Graphs
• Dynamic programming and pseudo-inverses
• From dynamic programming to bynamic programming
• scientific article; zbMATH DE number 1260458
• scientific article; zbMATH DE number 1431652
• Dynamic programming
• scientific article; zbMATH DE number 53073
• scientific article; zbMATH DE number 5866260

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3765164 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3555903 (Why is no real title available?)
• scientific article; zbMATH DE number 3630813 (Why is no real title available?)
• scientific article; zbMATH DE number 3428547 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• A New Pebble Game that Characterizes Parallel Complexity Classes
• An observation on time-storage trade off
• Fast Parallel Computation of Polynomials Using Few Processors
• Properties that characterize LOGCFL
• Speedups of deterministic machines by synchronous parallel machines
• The Pebbling Problem is Complete in Polynomial Space
• Tree-size bounded alternation
• Two Familiar Transitive Closure Algorithms Which Admit No Polynomial Time, Sublinear Space Implementations

Cited in

(4)

• The complexity of computing maximal word functions
• Rounds versus time for the two person pebble game (extended abstract)
• An infinite pebble game and applications
• The complexity of short two-person games

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2277375)