SIAM Journal on Computing, Volume 24

Volume 24, Number 1, February 1995

• Andreas Blass, Yuri Gurevich:
  Matrix Transformation Is Complete for the Average Case. 3-29
  
• Richard Cole, Ramesh Hariharan, Mike Paterson, Uri Zwick:
  Tighter Lower Bounds on the Exact Complexity of String Matching. 30-45
  
• Ming-Yang Kao:
  Planar Strong Connectivity Helps in Parallel Depth-First Search. 46-62
  
• Dario Bini, Luca Gemignani:
  Fast Parallel Computation of the Polynomial Remainder Sequence Via Bezout and Hankel Matrices. 63-77
  
• Noga Alon, Richard M. Karp, David Peleg, Douglas B. West:
  A Graph-Theoretic Game and Its Application to the k-Server Problem. 78-100
  
• Huzur Saran, Vijay V. Vazirani:
  Finding k Cuts within Twice the Optimal. 101-108
  
• Maria Luisa Bonet, Samuel R. Buss:
  The Serial Transitive Closure Problem for Trees. 109-122
  
• Oscar H. Ibarra, Tao Jiang, Nicholas Q. Trân, Hui Wang:
  New Decidability Results Concerning Two-Way Counter Machines. 123-137
  
• Yanjun Zhang:
  On the Optimality of Randomized alpha-beta Search. 138-147
  
• Israel Cidon, Shay Kutten, Yishay Mansour, David Peleg:
  Greedy Packet Scheduling. 148-157
  
• Moni Naor, Ron M. Roth:
  Optimal File Sharing in Distributed Networks. 158-183
  
• Paul J. Heffernan, Joseph S. B. Mitchell:
  An Optimal Algorithm for Computing Visibility in the Plane. 184-201
  

Volume 24, Number 2, April 1995

• Joseph Cheriyan, Torben Hagerup:
  A Randomized Maximum-Flow Algorithm. 203-226
  
• B. K. Natarajan:
  Sparse Approximate Solutions to Linear Systems. 227-234
  
• Qingzhou Wang, Ernst L. Leiss:
  A Heuristic Scheduling of Independent Tasks with Bottleneck Resource Constraints. 235-241
  
• Dima Grigoriev, Michael F. Singer, Andrew Chi-Chih Yao:
  On Computing Algebraic Functions Using Logarithms and Exponentials. 242-246
  
• Sanjiv Kapoor, H. Ramesh:
  Algorithms for Enumerating All Spanning Trees of Undirected and Weighted Graphs. 247-265
  
• Faith E. Fich, J. Ian Munro, Patricio V. Poblete:
  Permuting in Place. 266-278
  
• David W. Juedes, Jack H. Lutz:
  The Complexity and Distribution of Hard Problems. 279-295
  
• Michel X. Goemans, David P. Williamson:
  A General Approximation Technique for Constrained Forest Problems. 296-317
  
• Gilad Koren, Dennis Shasha:
  D^over: An Optimal On-Line Scheduling Algorithm for Overloaded Uniprocessor Real-Time Systems. 318-339
  
• Pekka Kilpeläinen, Heikki Mannila:
  Ordered and Unordered Tree Inclusion. 340-356
  
• Yishay Mansour:
  Randomized Interpolation and Approximation of Sparse Polynomials. 357-368
  
• Arthur L. Delcher, S. Rao Kosaraju:
  An NC Algorithm for Evaluating Monotone Planar Circuits. 369-375
  
• Benny Chor, Mihály Geréb-Graus, Eyal Kushilevitz:
  Private Computations over the Integers. 376-386
  
• Yagati N. Lakshman, B. David Saunders:
  Sparse Polynomial Interpolation in Nonstandard Bases. 387-397
  
• Ming Li, Paul M. B. Vitányi:
  A New Approach to Formal Language Theory by Kolmogorov Complexity. 398-410
  

Volume 24, Number 3, June 1995

• Wen-Lian Hsu:
  O(M*N) Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs. 411-439
  
• Ajit Agrawal, Philip N. Klein, R. Ravi:
  When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks. 440-456
  
• Chung-Do Yang, D. T. Lee, C. K. Wong:
  Rectilinear Path Problems among Rectilinear Obstacles Revisited. 457-472
  
• Jürg Ganz:
  Evaluation of Polynomials Using the Structure of the Coefficients. 473-483
  
• Alan M. Frieze, Richard M. Karp, Bruce A. Reed:
  When is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem? 484-493
  
• Andrew V. Goldberg:
  Scaling Algorithms for the Shortest Paths Problem. 494-504
  
• András A. Benczúr:
  Counterexamples for Directed and Node Capacitated Cut-Trees. 505-510
  
• Sampath Kannan, Tandy Warnow:
  Tree Reconstruction from Partial Orders. 511-519
  
• Raffaele Giancarlo:
  A Generalization of the Suffix Tree to Square Matrices, with Applications. 520-562
  
• Takeshi Tokuyama, Jun Nakano:
  Efficient Algorithms for the Hitchcock Transportation Problem. 563-578
  
• Edith Cohen:
  Approximate Max-Flow on Small Depth Networks. 579-597
  
• Richard A. Duke, Hanno Lefmann, Vojtech Rödl:
  A Fast Approximation Algorithm for Computing the Frequencies of Subgraphs in a Given Graph. 598-620
  
• Henri-M. Méjean, Henri Morel, Gerard Reynaud:
  A Variational Method for Analysing Unit Clause Search. 621-649
  
• Ioannis Z. Emiris, John F. Canny:
  A General Approach to Removing Degeneracies. 650-664
  
• Timothy Law Snyder, J. Michael Steele:
  A Priori Bounds on the Euclidean Traveling Salesman. 665-671
  

Volume 24, Number 4, August 1995

• Harry Buhrman, Edith Hemaspaandra, Luc Longpré:
  SPARSE Reduces Conjunctively to TALLY. 673-681
  
• Nader H. Bshouty, Richard Cleve, Wayne Eberly:
  Size-Depth Tradeoffs for Algebraic Formulas. 682-705
  
• Nader H. Bshouty, Thomas R. Hancock, Lisa Hellerstein:
  Learning Arithmetic Read-Once Formulas. 706-735
  
• Tomás Feder, Eyal Kushilevitz, Moni Naor, Noam Nisan:
  Amortized Communication Complexity. 736-750
  
• Håkan Lennerstad, Lars Lundberg:
  An Optimal Execution Time Estimate of Static Versus Dynamic Allocation in Multiprocessor Systems. 751-764
  
• Kazuo Murota:
  Computing the Degree of Determinants Via Combinatorial Relaxation. 765-796
  
• Donald W. Gillies, Jane W.-S. Liu:
  Scheduling Tasks with AND/OR Precedence Constraints. 797-810
  
• Victor Y. Pan, Franco P. Preparata:
  Work-Preserving Speed-Up of Parallel Matrix Computations. 811-821
  
• Svatopluk Poljak:
  Integer Linear Programs and Local Search for Max-Cut. 822-839
  
• Lane A. Hemaspaandra, Riccardo Silvestri:
  Easily Checked Generalized Self-Reducibility. 840-858
  
• Samir Khuller, Balaji Raghavachari, Neal E. Young:
  Approximating the Minimum Equivalent Digraph. 859-872
  
• Rodney G. Downey, Michael R. Fellows:
  Fixed-Parameter Tractability and Completeness I: Basic Results. 873-921
  

Volume 24, Number 5, October 1995

• Arthur W. Chou, Ker-I Ko:
  Computational Complexity of Two-Dimensional Regions. 923-947
  
• Mark Giesbrecht:
  Nearly Optimal Algorithms for Canonical Matrix Forms. 948-969
  
• Robert F. Cohen, Giuseppe Di Battista, Roberto Tamassia, Ioannis G. Tollis:
  Dynamic Graph Drawings: Trees, Series-Parallel Digraphs, and Planar ST-Digraphs. 970-1001
  
• Gary L. Miller, Joseph Naor:
  Flow in Planar Graphs with Multiple Sources and Sinks. 1002-1017
  
• Bernd Gärtner:
  A Subexponential Algorithm for Abstract Optimization Problems. 1018-1035
  
• Suresh Chari, Pankaj Rohatgi, Aravind Srinivasan:
  Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems. 1036-1050
  
• Franz Höfting, Egon Wanke:
  Minimum Cost Paths in Periodic Graphs. 1051-1067
  
• Mitsunori Ogihara:
  Polynomial-Time Membership Comparable Sets. 1068-1081
  
• Bin Fu:
  With Quasilinear Queries EXP Is Not Polynomial Time Turing Reducible to Sparse Sets. 1082-1090
  
• Arne Andersson, Thomas Ottmann:
  New Tight Bounds on Uniquely Represented Dictionaries. 1091-1101
  
• Ching-Chih Han, Kwei-Jay Lin, Jane W.-S. Liu:
  Scheduling Jobs with Temporal Distance Constraints. 1102-1121
  
• Tao Jiang, Ming Li:
  On the Approximation of Shortest Common Supersequences and Longest Common Subsequences. 1122-1139
  

Volume 24, Number 6, December 1995

• Luc Devroye, J. M. Robson:
  On the Generation of Random Binary Search Trees. 1141-1156
  
• Luc Devroye, Bruce A. Reed:
  On the Variance of the Height of Random Binary Search Trees. 1157-1162
  
• Lawrence L. Larmore, Teresa M. Przytycka:
  Constructing Huffman Trees in Parallel. 1163-1169
  
• Jack H. Lutz:
  Weakly Hard Problems. 1170-1189
  
• Adam L. Buchsbaum, Rajamani Sundar, Robert Endre Tarjan:
  Data-Structural Bootstrapping, Linear Path Compression, and Catenable Heap-Ordered Double-Ended Queues. 1190-1206
  
• R. C. Sekar, R. Ramesh, I. V. Ramakrishnan:
  Adaptive Pattern Matching. 1207-1234
  
• Alberto O. Mendelzon, Peter T. Wood:
  Finding Regular Simple Paths in Graph Databases. 1235-1258
  
• Moni Naor, Larry J. Stockmeyer:
  What Can be Computed Locally? 1259-1277
  
• Thomas Eiter, Georg Gottlob:
  Identifying the Minimal Transversals of a Hypergraph and Related Problems. 1278-1304
  
• K. Kalorkoti:
  On the Reuse of Additions in Matrix Multiplication. 1305-1312
  
• David B. Shmoys, Joel Wein, David P. Williamson:
  Scheduling Parallel Machines On-Line. 1313-1331
  
• Xiaofeng Han, Pierre Kelsen, Vijaya Ramachandran, Robert Endre Tarjan:
  Computing Minimal Spanning Subgraphs in Linear Time. 1332-1358
  

Last update Tue Feb 14 04:22:17 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page