SIAM Journal on Computing, Volume 15

Volume 15, Number 1, February 1986

• Guy W. Cherry:
  Integration in Finite Terms with Special Functions: The Logarithmic Integral. 1-21
  
• Kurt Mehlhorn, Athanasios K. Tsakalidis:
  An Amortized Analysis of Insertions into AVL-Trees. 22-33
  
• Joseph O'Rourke:
  The Signature of a Plane Curve. 34-51
  
• Daniel Dominic Sleator, Robert Endre Tarjan:
  Self-Adjusting Heaps. 52-69
  
• Joost Engelfriet:
  The complexity of Languages Generated by Attribute Grammars. 70-86
  
• Stephen A. Cook, Cynthia Dwork, Rüdiger Reischuk:
  Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes. 87-97
  
• Alberto Apostolico, Raffaele Giancarlo:
  The Boyer-Moore-Galil String Searching Strategies Revisited. 98-105
  
• Friedhelm Meyer auf der Heide:
  Efficient Simulations Among Several Models of Parallel Computers. 106-119
  
• Zvi Galil, Silvio Micali, Harold N. Gabow:
  An O(EV log V) Algorithm for Finding a Maximal Weighted Matching in General Graphs. 120-130
  
• Francis Y. L. Chin, K. V. S. Ramarao:
  Optimal Termination Protocols for Network Partitioning. 131-144
  
• Mike Shub, Steve Smale:
  Computational Complexity: On the Geometry of Polynomials and a Theory of Cost: II. 145-161
  
• Brenda S. Baker:
  A Provably Good Algorithm for the Two Module Routing Problem. 162-188
  
• Don Coppersmith, Maria M. Klawe, Nicholas Pippenger:
  Alphabetic Minimax Trees of Degree at Most t. 189-192
  
• Micha Sharir, Amir Schorr:
  On Shortest Paths in Polyhedral Spaces. 193-215
  
• Tuvi Etzion, Abraham Lempel:
  An Efficient Algorithm for Generating Linear Transformations in a Shuffle-Exchange Network. 216-221
  
• Donald K. Friesen, Michael A. Langston:
  Variable Sized Bin Packing. 222-230
  
• John H. Reif:
  Logarithmic Depth Circuits for Algebraic Functions. 231-242
  
• Stanley Cabay, Dong-Koo Choi:
  Algebraic Computations of Scaled Padé Fractions. 243-270
  
• Herbert Edelsbrunner, Emo Welzl:
  Constructing Belts in Two-Dimensional Arrangements with Applications. 271-284
  
• Leonid A. Levin:
  Average Case Complete Problems. 285-286
  
• David G. Kirkpatrick, Raimund Seidel:
  The Ultimate Planar Convex Hull Algorithm? 287-299
  
• Bernard Chazelle, Robert L. (Scot) Drysdale III, D. T. Lee:
  Computing the Largest Empty Rectangle. 300-315
  

Volume 15, Number 2, May 1986

• Herbert Edelsbrunner, Leonidas J. Guibas, Jorge Stolfi:
  Optimal Point Location in a Monotone Subdivision. 317-340
  
• Herbert Edelsbrunner, Joseph O'Rourke, Raimund Seidel:
  Constructing Arrangements of Lines and Hyperplanes with Applications. 341-363
  
• Lenore Blum, Manuel Blum, Mike Shub:
  A Simple Unpredictable Pseudo-Random Number Generator. 364-383
  
• Lenore Blum, Mike Shub:
  Evaluating Rational Functions: Infinite Precision is Finite Cost and Tractable on Average. 384-398
  
• Pekka Orponen, David A. Russo, Uwe Schöning:
  Optimal Approximations and Polynomially Levelable Sets. 399-408
  
• John L. Bruno, Peter J. Downey:
  Probabilistic Bounds on the Performance of List Scheduling. 409-417
  
• Giorgio Ausiello, Alessandro D'Atri, Domenico Saccà:
  Minimal Representation of Directed Hypergraphs. 418-431
  
• Joachim von zur Gathen:
  Representations and Parallel Computations for Rational Functions. 432-452
  
• Wolfgang Maass:
  On the Complexity of Nonconvex Covering. 453-467
  
• Dan E. Willard:
  Log-Logarithmic Selection Resolution Protocols in a Multiple Access Channel. 468-477
  
• Hiroshi Imai, Takao Asano:
  Efficient Algorithms for Geometric Graph Search Problems. 478-494
  
• Kazuhiko Matsumoto, Takao Nishizeki, Nobuji Saito:
  Planar Multicommodity Flows, Maximum Matchings and Negative Cycles. 495-510
  
• John G. Geske, Joachim Grollmann:
  Relativizations of Unambiguous and Random Polynomial Time Classes. 511-519
  
• Carl Langenhop, William E. Wright:
  Probabilities Related to Father-Son Distances in Binary Search Trees. 520-530
  
• Leslie G. Valiant:
  Negation is Powerless for Boolean Slice Functions. 531-535
  
• Alan M. Frieze:
  On the Lagarias-Odlyzko Algorithm for the Subset Sum Problem. 536-539
  
• Robert Alan Wright, L. Bruce Richmond, Andrew M. Odlyzko, Brendan D. McKay:
  Constant Time Generation of Free Trees. 540-548
  
• Allan Borodin, Danny Dolev, Faith E. Fich, Wolfgang J. Paul:
  Bounds for Width Two Branching Programs. 549-560
  
• Jonathan S. Turner:
  On the Probable Performance of Heuristics for Bandwidth Minimization. 561-580
  
• Dung T. Huynh:
  The Complexity of the Membership Problem for Two Subclasses of Polynomial Ideals. 581-594
  
• Rodney W. Johnson, Aileen M. McLoughlin:
  Noncommutative Bilinear Algorithms for 3 x 3 Matrix Multiplication. 595-603
  
• Francine Berman, Mary Ellen Bock, Eric Dittert, Michael J. O'Donnell, Darrell Plank:
  Collections of Functions for Perfect Hashing. 604-618
  
• Joan Feigenbaum, Alejandro A. Schäffer:
  Recognizing Composite Graphs is Equivalent to Testing Graph Isomorphism. 619-627
  

Volume 15, Number 3, August 1986

• Philippe Flajolet, Helmut Prodinger:
  Register Allocation for Unary-Binary Trees. 629-640
  
• Joel Friedman:
  Constructing O(n log n) Size Monotone Formulae for the k-th Threshold Function of n Boolean Variables. 641-654
  
• Robert W. Irving, Paul Leather:
  The Complexity of Counting Stable Marriages. 655-667
  
• Claudio Citrini, Stefano Crespi-Reghizzi, Dino Mandrioli:
  On Deterministic Multi-Pass Analysis. 668-693
  
• J. Scott Provan:
  The Complexity of Reliability Computations in Planar and Acyclic Graphs. 694-702
  
• Bernard Chazelle:
  Filtering Search: A New Approach to Query-Answering. 703-724
  
• Martin E. Dyer:
  On a Multidimensional Search Technique and its Application to the Euclidean One-Centre Problem. 725-738
  
• José L. Balcázar, Ronald V. Book, Uwe Schöning:
  Sparse Sets, Lowness and Highness. 739-747
  
• Philippe Flajolet, Robert Sedgewick:
  Digital Search Trees Revisited. 748-767
  
• John E. Hopcroft, Gordon T. Wilfong:
  Reducing Multiple Object Motion Planning to Graph Searching. 768-785
  
• Friedrich Otto:
  Church-Rosser Thue Systems that Present Free Monoids. 786-792
  
• Frank Thomson Leighton, Arnold L. Rosenberg:
  Three-Dimensional Circuit Layouts. 793-813
  
• Justin R. Smith:
  Parallel Algorithms for Depth-First Searches I. Planar Graphs. 814-830
  
• Harry B. Hunt III, Daniel J. Rosenkrantz:
  Recursion Schemes and Recursive Programs are Exponentially Hard to Analyze. 831-850
  
• Benjamin Arazi:
  A Binary Search with a Parallel Recovery of the Bits. 851-855
  
• Richard Hull:
  Relative Information Capacity of Simple Relational Database Schemata. 856-886
  
• Jeffrey H. Kingston:
  Analysis of Henriksen's Algorithm for the Simulation Event Set. 887-902
  

Volume 15, Number 4, November 1986

• James H. Davenport:
  The Risch Differential Equation Problem. 903-918
  
• Martin David Katz, Dennis J. Volper:
  Data Structures for Retrieval on Square Grids. 919-931
  
• King F. Pang, Abbas El Gamal:
  Communication Complexity of Computing the Hamming Distance. 932-947
  
• William H. Cunningham:
  Improved Bounds for Matroid Partition and Intersection Algorithms. 948-957
  
• Klaus Ambos-Spies:
  An Inhomogeneity in the Structure of Karp Degrees. 958-963
  
• Gaston H. Gonnet, J. Ian Munro:
  Heaps on Heaps. 964-971
  
• David Prill:
  On Approximations and Incidence in Cylindrical Algebraic Decompositions. 972-993
  
• Paul Beame, Stephen A. Cook, H. James Hoover:
  Log Depth Circuits for Division and Related Problems. 994-1003
  
• Joseph JáJá, Jean Takche:
  On the Validity of the Direct Sum Conjecture. 1004-1020
  
• Norbert Blum:
  On the Single-Operation Worst-Case Time Complexity of the Disjoint Set Union Problem. 1021-1024
  
• Liwu Li:
  Ranking and Unranking of AVL-Trees. 1025-1035
  
• Michael Luby:
  A Simple Parallel Algorithm for the Maximal Independent Set Problem. 1036-1053
  
• Egon Balas, Chang Sung Yu:
  Finding a Maximum Clique in an Arbitrary Graph. 1054-1068
  
• Daniel S. Hirschberg, Lawrence L. Larmore:
  Average Case Analysis of Marking Algorithms. 1069-1074
  
• Ulrich Faigle, László Lovász, Rainer Schrader, György Turán:
  Searching in Trees, Series-Parallel and Interval Orders. 1075-1084
  
• Donald P. Gaver, Patricia A. Jacobs:
  Processor-Shared Time-Sharing Models in Heavy Traffic. 1085-1100
  
• Dung T. Huynh:
  Some Observations about the Randomness of Hard Problems. 1101-1105
  
• Ming-Te Chao, John V. Franco:
  Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem. 1106-1118
  
• Tsuyoshi Kawaguchi, Seiki Kyan:
  Worst Case Bound of an LRF Schedule for the Mean Weighted Flow-Time Problem. 1119-1129
  
• Udi Manber:
  On Maintaining Dynamic Information in a Concurrent Environment. 1130-1142
  
• Eric Bach, Gary L. Miller, Jeffrey Shallit:
  Sums of Divisors, Perfect Numbers and Factoring. 1143-1154
  
• Jean-Pierre Jouannaud, Hélène Kirchner:
  Completion of a Set of Rules Modulo a Set of Equations. 1155-1194
  

Last update Wed May 22 18:17:24 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page