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, (see: 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, (see: 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

last updated on Sat May 25 06:37:36 2013 by the dblp team
data released under the ODC-BY 1.0 license
see also our legal information page