×
Paul, W. J.; Tarjan, R. E.

Time-space trade-offs in a pebble game. (English) Zbl 0399.05030

Acta Inf. 10, 111-115 (1978).
Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0399.05030

Cited in 1 Review
Cited in 11 Documents

MSC:

05C20 Directed graphs (digraphs), tournaments
91A99 Game theory
68Q25 Analysis of algorithms and problem complexity
05-04 Software, source code, etc. for problems pertaining to combinatorics

Keywords:

Complexity; One Person Game; Graphs; PebBle Game; Directed Acyclic Graphs
Cite Review PDF
Full Text: DOI

References:

[1] Cook, S.A.: An observation on time-storage trade off. Proceedings Fifth Annual ACM Symp. on Theory of Computing, pp. 29-33, 1973 · Zbl 0305.68066
[2] Hopcroft, J., Paul, W., Valiant, L.: On time versus space. J. Assoc. Comput. Mach. 24, 332-337 (1977) · Zbl 0358.68082
[3] Paterson, M.S., Hewitt, C.E.: Comparative schematology. Record of Project MAC Conference on Concurrent Systems and Parallel Computation, pp. 119-128, 1970 · Zbl 0401.68002
[4] Paul, W., Tarjan, R.E., Celoni, J.R.: Space bounds for a game on graphs. Math. Systems Theory 10, 239-251 (1977) · Zbl 0366.90150 · doi:10.1007/BF01683275
[5] Pinsker, M.S.: On the complexity of a concentrator. 7th International Teletraffic Congress, Stockholm, 1973 · Zbl 0327.94051
[6] Pippenger, N.: Superconcentrators. Technical Report, IBM Thomas J. Watson Research Center, Yorktown Heights, N.Y., 1976 · Zbl 0361.05035
[7] Pippenger, N.: A time-space trade off. Technical Report, IBM Thomas J. Watson Research Center, Yorktown, Heights, N.Y., 1977 · Zbl 0379.68009
[8] Sethi, R.: Complete register allocation problems. SIAM J. Comput. 4, 226-248 (1975) · Zbl 0327.68042 · doi:10.1137/0204020
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.