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