Theory of Computing Systems, Volume 31

Volume 31, Number 1, January/February 1998

Daniel Hammer, Alexander Shen:
A Strange Application of Kolmogorov Complexity. 1-4
Fabrizio Luccio, Linda Pagli:
Computing with Time-Varying Data: Sequential Complexity and Parallel Speed-Up. 5-26
Sanjay Gupta:
Isolating an Odd Number of Elements and Applications in Complexity Theory. 27-40
Amir Ben-Dor, Shai Halevi, Assaf Schuster:
Potential Function Analysis of Greedy Hot-Potato Routing. 41-61
Frank K. Hwang, Y. C. Yao:
Comments on the Oblivious Routing Algorithm of Kaklamanis, Krizanc, and Tsantilas in the Hypercube. 63-66
Jin-yi Cai:
Frobenius's Degree Formula and Toda's Polynomials. 67-75
Harry Buhrman, Jim Kadin, Thomas Thierauf:
Functions Computable with Nonadaptive Queries to NP. 77-92
K. Cronauer, Ulrich Hertrampf, Heribert Vollmer, Klaus W. Wagner:
The Chain Method to Separate Counting Classes. 93-108

M. Hollander:
Greedy Numeration Systems and Regularity. 111-133
Guy E. Blelloch, Charles E. Leiserson:
An Experimental Analysis of Parallel. 135-167
Bruce M. Maggs, C. Greg Plaxton, Stephen J. Smith, Marco Zagha: Sorting Algorithms. 135-167
Fabien Durand:
A Generalization of Cobham's Theorem. 169-185
Stephen A. Bloch, Jonathan F. Buss, Judy Goldsmith:
Sharply Bounded Alternation and Quasilinear Time. 187-214

Ludwig Staiger:
A. Tight Upper Bound on Kolmogorov Complexity and Uniformly Optimal Prediction. 215-229
Marc Gemis, Jan Paredaens, Peter Peelman, Jan Van den Bussche:
Expressiveness and Complexity of Generic Graph Machines. 231-249
Thomas H. Cormen, Kristin Bruhl:
Don't Be Too Clever: Routing BMMC Permutations on the MasPar MP-2. 251-278
Abdelmadjid Bouabdallah, Marie-Claude Heydemann, Jaroslav Opatrny, Dominique Sotteau:
Embedding Complete Binary Trees Into Star and Pancake Graphs. 279-305
Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel:
R^{S N}_1-tt (NP) Distinguishes Robust Many-One and Turing Completeness. 307-325

Special Issue: ACM Symposium on Parallel Algorithms and Architectures (SPAA 1996)

S. Muthukrishnan, Bhaskar Ghosh, Martin H. Schultz:
First- and Second-Order Diffusive Methods for Rapid, Coarse, Distributed Load Balancing. 331-354
Seungjoon Park, David L. Dill:
Verification of Cache Coherence Protocols by Aggregation of Distributed Transactions. 355-376
Micah Adler:
Asynchronous Shared Memory Search Structures. 377-401
Nir Shavit, Eli Upfal, Asaph Zemach:
A Steady State Analysis of Diffracting Trees. 403-423
Christian Scheideler, Berthold Vöcking:
Universal Continuous Routing Strategies. 425-449
Liviu Iftode, Jaswinder Pal Singh, Kai Li:
Scope Consistency: A Bridge between Release Consistency and Entry Consistency. 451-473
Aythan Avior, Tiziana Calamoneri, Shimon Even, Ami Litman, Arnold L. Rosenberg:
A Tight Layout of the Butterfly Network. 475-488

Special Issue: Seventh International Symposium on Algorithms and Computation

Tzuoo-Hawn Yeh, Cheng-Ming Kuo, Chin-Laung Lei, Hsu-Chun Yen:
Competitive Analysis of On-Line Disk Scheduling. 491-506
Andrzej Lingas, V. Soltan:
Minimum Convex Partition of a Polygon with Holes by Cuts in Given Directions. 507-538
Eric Allender, Klaus-Jörn Lange:
RUSPACE(log n) $\subseteq$ DSPACE (log² n / log log n). 539-550
Miroslaw Kutylowski, Krzysztof Lorys, Brigitte Oesterdiekhoff:
Periodic Merging Networks. 551-578
Kazuyoshi Hayase, Hiroshi Imai:
OBDDs of a Monotone Function and Its Prime Implicants. 570-591
Tatsuya Hayashi, Koji Nakano, Stephan Olariu:
Efficient List Ranking on the Reconfigurable Mesh with Applications. 593-611
Mark de Berg, Otfried Cheong, Olivier Devillers, Marc J. van Kreveld, Monique Teillaud:
Computing the Maximum Overlap of Two Convex Polygons under Translations. 613-628

Lenwood S. Heath, John Paul C. Vergara:
Edge-Packing in Planar Graphs. 629-662
F. Fagnani, Luciano Margara:
Expansivity, Permutivity, and Chaos for Cellular Automata. 663-677
Bernd Borchert, Desh Ranjan, Frank Stephan:
On the Computational Complexity of Some Classical Equivalence Relations on Boolean Functions. 679-693

Last update Mon May 20 18:14:16 2013 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page