SIAM Journal on Computing, Volume 10
Volume 10, Number 1, February 1981
- John H. Rowland, Philip J. Davis:
On the Selection of Test Data for Recursive Mathematical Subroutines. 59-72 - Charles H. Bennett, John Gill:
Relative to a Random Oracle A, PA != NPA != co-NPA with Probability 1. 96-113 - Stefano Crespi-Reghizzi, Giovanni Guida, Dino Mandrioli:
Operator Precedence Grammars and the Noncounting Property. 174-191 - M. I. Dessouky, Jitender S. Deogun:
Sequencing Jobs with Unequal Ready Times to Minimize Mean Flow Time. 192-202 - Charles J. Colbourn, Kellogg S. Booth:
Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs. 203-225
Volume 10, Number 2, May 1981
- Naoki Katoh, Toshihide Ibaraki, Hisashi Mine:
An Algorithm for Finding K Minimum Spanning Trees. 247-255 - M. R. Garey, David S. Johnson, Barbara B. Simons, Robert Endre Tarjan:
Scheduling Unit-Time Tasks with Arbitrary Release Times and Deadlines. 256-269 - Greg N. Frederickson, Joseph JáJá:
Approximation Algorithms for Several Graph Augmentation Problems. 270-283 - Luc Boasson, Bruno Courcelle, Maurice Nivat:
The Rational Index: A Complexity Measure for Languages. 284-296 - Nimrod Megiddo, Arie Tamir, Eitan Zemel, R. Chandrasekaran:
An O(n log2 n) Algorithm for the k-th Longest Path in a Tree with Applications to Location Problems. 328-337 - Catriel Beeri, Alberto O. Mendelzon, Yehoshua Sagiv, Jeffrey D. Ullman:
Equivalence of Relational Database Schemes. 352-370 - Juris Hartmanis, Stephen R. Mahaney:
Languages Simultaneously Complete for One-Way and Two-Way Log-Tape Automata. 383-390
Volume 10, Number 3, August 1981
- Alfred V. Aho, Yehoshua Sagiv, Thomas G. Szymanski, Jeffrey D. Ullman:
Inferring a Tree from Lowest Common Ancestors with an Application to the Optimization of Relational Expressions. 405-421 - Richard Schroeppel, Adi Shamir:
A T=O(2n/2), S=O(2n/4) Algorithm for Certain NP-Complete Problems. 456-464 - Christos H. Papadimitriou:
Worst-Case and Probabilistic Analysis of a Geometric Location Problem. 542-557 - James R. Bitner, Shou-Hsuan Stephen Huang:
Key Comparison Optimal 2-3 Trees with Maximum Utilization. 558-570 - Stephen A. Cook:
Corrigendum: Soundness and Completeness of an Axiom System for Program Verification. 612
Volume 10, Number 4, November 1981
- Peter J. Slater, Ernest J. Cockayne, Stephen T. Hedetniemi:
Information Dissemination in Trees. 692-701 - Sam Toueg, Kenneth Steiglitz:
Some Complexity Results in the Design of Deadlock-Free Packet Switching Networks. 702-712 - Charles Rackoff, Joel I. Seiferas:
Limitations on Separating Nondeterministic Complexity Classes. 742-745 - Alon Itai, Richard J. Lipton, Christos H. Papadimitriou, Michael Rodeh:
Covering Graphs by Simple Circuits. 746-750 - Kari-Jouko Räihä, Esko Ukkonen:
Minimizing the Number of Evaluation Passes for Attribute Grammars. 772-786 - Maciej M. Syslo:
An Efficient Cycle Vector Space Algorithm for Listing all Cycles of a Planar Graph. 797-808