Volume 23, Number 1, February 1994
- Dima Grigoriev, Marek Karpinski, Michael F. Singer:
Computational Complexity of Sparse Rational Interpolation.
1-11
- Alfredo De Santis, Giuseppe Persiano:
Tight Upper and Lower Bounds on the Path Length of Binary Trees.
12-23
- Rajamani Sundar, Robert Endre Tarjan:
Unique Binary-Search-Tree Representations and Equality Testing of Sets and Sequences.
24-44
- Endre Boros, Yves Crama, Peter L. Hammer, Michael E. Saks:
A Complexity Index for Satisfiability Problems.
45-49
- Alberto Apostolico, Giuseppe F. Italiano, Giorgio Gambosi, Maurizio Talamo:
The Set Union Problem With Unlimited Backtracking.
50-70
- David Kuo, Gerard J. Chang:
The Profile Minimization Problem in Trees.
71-81
- Ding-Zhu Du, Guoliang Xue, S.-Z. Sun, Siu-Wing Cheng:
Modifications of Competitive Group Testing.
82-96
- Mihir Bellare, Shafi Goldwasser:
The Complexity of Decision Versus Search.
97-119
- John Shawe-Taylor, Tomaz Pisanski:
Homeomorphism of 2-Complexes is Graph Isomorphism Complete.
120-132
- Marco Pellegrini:
On Collision-Free Placements of Simplices and the Closest Pair of Lines in 3-Space.
133-153
- Jirí Matousek, János Pach, Micha Sharir, Shmuel Sifrony, Emo Welzl:
Fat Triangles Determine Linearly Many Holes.
154-169
- Robert W. Irving, Mark Jerrum:
Three-Dimensional Statistical Data Security Problems.
170-184
- Greg N. Frederickson, Susan H. Rodger:
An NC Algorithm for Scheduling Unit-Time Jobs With Arbitrary Release Times and Deadlines.
185-211
- Jean-Claude Bermond, Pierre Fraigniaud:
Broadcasting and Gossiping in de Bruijn Networks.
212-225
Volume 23, Number 2, April 1994
- Michael Kaufmann, Kurt Mehlhorn:
A Linear-Time Algorithm for the Homotopic Routing Problem in Grid Graphs.
227-246
- Eberhard Triesch:
Some Results on Elusive Graph Properties.
247-254
- Bin Fu, Hong-Zhou Li:
Closeness of NP-Hard Sets to Other Complexity Classes.
255-260
- Johannes Köbler, Thomas Thierauf:
Complexity-Restricted Advice Functions.
261-275
- Kieran T. Herley, Gianfranco Bilardi:
Deterministic Simulations of PRAMs on Bounded Degree Networks.
276-292
- Howard J. Karloff, Yuval Rabani, Yiftach Ravid:
Lower Bounds for Randomized k-Server and Motion-Planning Algorithms.
293-312
- Amihood Amir, Gary Benson, Martin Farach:
An Alphabet Independent Approach to Two-Dimensional Pattern Matching.
313-323
- Andrei Z. Broder, Anna R. Karlin, Prabhakar Raghavan, Eli Upfal:
Trading Space for Time in Undirected s-t Connectivity.
324-334
- Soma Chaudhuri, Jennifer L. Welch:
Bounds on the Costs of Multivalued Register Implementations.
335-354
- Anindo Bagchi, Edward F. Schmeichel, S. Louis Hakimi:
Parallel Information Dissemination by Packets.
355-372
- Gara Pruesse, Frank Ruskey:
Generating Linear Extensions Fast.
373-386
- H. Narayanan, Huzur Saran, Vijay V. Vazirani:
Randomized Parallel Algorithms for Matroid Union and Intersection, With Applications to Arboresences and Edge-Disjoint Spanning Trees.
387-397
- R. Swaminathan, Donald K. Wagner:
On the Consecutive-Retrieval Problem.
398-414
- Myong-Hi Kim, Scott Sutherland:
Polynomial Root-Finding Algorithms and Branched Covers.
415-436
- Mark de Berg, Mark H. Overmars, Otfried Schwarzkopf:
Computing and Verifying Depth Orders.
437-446
- John H. Reif, Sandeep Sen:
Erratum: Optimal Parallel Randomized Algorithms for Three-Dimensional Convex Hulls and Related Problems.
447-448 ,
->SIAM J. Comput. 21(3): 466-485(1992)
Volume 23, Number 3, June 1994
- Omer Berkman, Joseph JáJá, Sridhar Krishnamurthy, Ramakrishna Thurimella, Uzi Vishkin:
Top-Bottom Routing Around a Rectangle is as Easy as Computing Prefix Minima.
449-465
- Philip N. Klein, Serge A. Plotkin, Clifford Stein, Éva Tardos:
Faster Approximation Algorithms for the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts.
466-487
- Ming-Jye Sheu, Timothy J. Long:
The Extended Low Hierarchy is an Infinite Hierarchy.
488-509
- Donald B. Johnson, Larry Raab:
Complexity of Network Reliability and Optimal Resource Placement Problems.
510-519
- Jitender S. Deogun, George Steiner:
Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs.
520-552
- Victor Pestien, Subramanian Ramakrishnan, Dilip Sarkar:
Packet Transmission in a Noisy-Channel Ring Network.
553-562
- Jin-yi Cai, Richard J. Lipton:
Subquadratic Simulations of Balanced Formulae by Branching Programs.
563-572
- Etienne Grandjean:
Linear Time Algorithms and NP-Complete Problems.
573-597
- Peter Kirschenhofer, Helmut Prodinger, Wojciech Szpankowski:
Digital Search Trees Again Revisited: The Internal Path Length Perspective.
598-616
- David B. Shmoys, Clifford Stein, Joel Wein:
Improved Approximation Algorithms for Shop Scheduling Problems.
617-632
- John H. Reif, Sandeep Sen:
Randomized Algorithms for Binary Search and Load Balancing on Fixed Connection Networks with Geometric Applications.
633-651
- Paul Beame, Martin Tompa, Peiyuan Yan:
Communication-Space Tradeoffs for Unrestricted Protocols.
652-661
- Bertrand Braschi, Denis Trystram:
A New Insight into the Coffman-Graham Algorithm.
662-669
Volume 23,
Number 4,
August 1994
- Ashok Subramanian:
A New Approach to Stable Matching Problems.
671-700
- Benny Chor, Amos Israeli, Ming Li:
Wait-Free Consensus Using Asynchronous Hardware.
701-712
- Sampath Kannan, Tandy Warnow:
Inferring Evolutionary History from DNA Sequences.
713-737
- Martin Dietzfelbinger, Anna R. Karlin, Kurt Mehlhorn, Friedhelm Meyer auf der Heide, Hans Rohnert, Robert Endre Tarjan:
Dynamic Perfect Hashing: Upper and Lower Bounds.
738-761
- Jack H. Lutz, Elvira Mayordomo:
Measure, Stochasticity, and the Density of Hard Languages.
762-779
- Alexander Schrijver:
Finding k Disjoint Paths in a Directed Planar Graph.
780-788
- Karel Culik II, Juhani Karhumäki:
Finite Automata Computing Real Functions.
789-814
- Nader H. Bshouty:
On the Complexity of Bilinear Forms over Associative Algebras.
815-833
- Prakash V. Ramanan:
A New Lower Bound Technique and its Application: Tight Lower Bound for a Polygon Triangulation Problem.
834-851
- Luca Aceto:
On "Axiomatising Finite Concurrent Processes".
852-863 ,
->SIAM J. Comput. 17(5): 997-1017(1988)
- Elias Dahlhaus, David S. Johnson, Christos H. Papadimitriou, Paul D. Seymour, Mihalis Yannakakis:
The Complexity of Multiterminal Cuts.
864-894
Volume 23,
Number 5,
October 1994
- Anindya Das, Krishnaiyan Thulasiraman, Vinod K. Agarwal:
Diagnosis of t/(t+1)-Diagnosable Systems.
895-905
- Ravindra K. Ahuja, James B. Orlin, Clifford Stein, Robert Endre Tarjan:
Improved Algorithms for Bipartite Network Flow.
906-933
- Victor Y. Pan:
New Resultant Inequalities and Complex Polynomial Factorization.
934-950
- Jeffery Westbrook:
Randomized Algorithms for Multiprocessor Page Migration.
951-965
- Andrew Chi-Chih Yao:
Near-Optimal Time-Space Tradeoff for Element Distinctness.
966-975
- Andrei Z. Broder, Alan M. Frieze, Eli Upfal:
Existence and Construction of Edge-Disjoint Paths on Expander Graphs.
976-989
- Avrim Blum:
Separating Distribution-Free and Mistake-Bound Learning Models over the Boolean Domain.
990-1000
- Uriel Feige, Prabhakar Raghavan, David Peleg, Eli Upfal:
Computing with Noisy Information.
1001-1018
- Ding-Zhu Du, Haesun Park:
On Competitive Group Testing.
1019-1025
- Eric Allender, Vivek Gore:
A Uniform Circuit Lower Bound for the Permanent.
1026-1049
- William Lew, Hosam M. Mahmoud:
The Joint Distribution of Elastic Buckets in Multiway Search Trees.
1050-1074
- Richard Cole:
Tight Bounds on the Complexity of the Boyer-Moore String Matching Algorithm.
1075-1091
Volume 23,
Number 6,
December 1994
- Marc Gyssens, Jan Paredaens, Dirk Van Gucht:
A Grammar-Based Approach Towards Unifying Hierarchical Data Models.
1093-1137
- Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, John Hershberger, Raimund Seidel, Micha Sharir:
Selecting Heavily Covered Points.
1138-1151
- Yehuda Afek, Eli Gafni:
Distributed Algorithms for Unidirectional Networks.
1152-1178
- Dorit S. Hochbaum, Joseph Naor:
Simple and Fast Algorithms for Linear and Integer Programs With Two Variables per Inequality.
1179-1192
- Sam M. Kim, Robert McNaughton:
Computing the Order of a Locally Testable Automaton.
1193-1215
- Richa Agarwala, David Fernández-Baca:
A Polynomial-Time Algorithm for the Perfect Phylogeny Problem when the Number of Character States is Fixed.
1216-1224
- M. D. Atkinson, Robert Beals:
Priority Queues and Permutations.
1225-1230
- Naomi Nishimura:
A Model for Asynchronous Shared Memory Parallel Computation.
1231-1252
- Shiva Chaudhuri:
Tight Pounds on Oblivious Chaining.
1253-1265
- Robert Cypher, Luis Gravano:
Requirements for Deadlock-Free, Adaptive Packet Routing.
1266-1274
- Ronald V. Book:
On Languages Reducible to Algorithmically Random Languages.
1275-1282
- Lawrence L. Larmore, Teresa M. Przytycka:
A Fast Algorithm for Optimum Height-Limited Alphabetic Binary Trees.
1283-1312
- Edith Cohen, Nimrod Megiddo:
Improved Algorithms for Linear Inequalities With Two Variables per Inequality.
1313-1347
Copyright © Wed Nov 11 05:34:11 2009
by Michael Ley (ley@uni-trier.de)
