default search action
SIAM Journal on Computing, Volume 22
Volume 22, Number 1, February 1993
- Amos Fiat, Moni Naor:
Implicit O(1) Probe Search. 1-10 - Zvi Galil, Giuseppe F. Italiano:
Maintaining the 3-Edge-Connected Components of a Graph On-Line. 11-28 - Héctor J. Hernández, Ke Wang:
On the Boundedness of Constant-Time-Maintainable Database Schemes. 29-45 - Weizhen Mao:
Tight Worst-Case Performance Bounds for Next-k-Fit Bin Packing. 46-56 - Greg N. Frederickson:
A Note on the Complexity of a Simple Transportation Problem. 57-61 - Robert Cypher:
A Lower Bound on the Size of Shellsort Sorting Networks. 62-71 - Joel Friedman
:
A Note on Poset Geometries. 72-78 - Sukhamay Kundu:
An O(n) Algorithm for Determining the Subregion-Tree Representation of a Rectangular Dissection. 79-101 - Viliam Geffert:
Tally Versions of the Savitch and Immerman-Szelepcsenyi Theorems for Sublogarithmic Space. 102-113 - Michio Oyamaguchi:
NV-Sequentiality: A Decidable Condition for Call-by-Need Computations in Term-Rewriting Systems. 114-135 - Kazuo Iwama:
ASPACE(o(log log n)) is Regular. 136-146 - Peter Bro Miltersen:
The Complexity of Malign Measures. 147-156 - Joseph Cheriyan, Ming-Yang Kao, Ramakrishna Thurimella:
Scan-First Search and Sparse Certificates: An Improved Parallel Algorithms for k-Vertex Connectivity. 157-174 - Andreas Weber:
Decomposing Finite-Valued Transducers and Deciding Their Equivalence. 175-202 - Jan Kratochvíl, Petr Savický, Zsolt Tuza:
One More Occurrence of Variables Makes Satisfiability Jump From Trivial to NP-Complete. 203-210 - Noam Nisan, Avi Wigderson:
Rounds in Communication Complexity Revisited. 211-219
Volume 22, Number 2, April 1993
- Omer Berkman, Uzi Vishkin:
Recursive Star-Tree Parallel Data Structure. 221-242 - Jorma Tarhio
Approximate Boyer-Moore String Matching. 243-260 - Wenceslas Fernandez de la Vega, Sampath Kannan, Miklos Santha:
Two Probabilistic Results on Merging. 261-271 - Wayne Goddard, Claire Kenyon, Valerie King, Leonard J. Schulman
Optimal Randomized Algorithms for Local Sorting and Set-Maxima. 272-283 - Narendra Karmarkar, Richard M. Karp, Richard J. Lipton, László Lovász, Michael Luby:
A Monte-Carlo Algorithm for Estimating the Permanent. 284-293 - Miklos Santha, Christopher B. Wilson:
Limiting Negations in Constant Depth Circuits. 294-302 - Khaled M. Bugrara, Paul Walton Purdom Jr.:
Average Time Analysis of Clause Order Backtracking. 303-317 - Chandrajit L. Bajaj, John F. Canny, Thomas Garrity, Joe D. Warren:
Factoring Rational Polynomials Over the Complex Numbers. 318-331 - Edward G. Coffman Jr., Leopold Flatto, Paul E. Wright:
Optimal Stochastic Allocation of Machines Under Waiting-Time Constraints. 332-348 - Gábor Galambos, Gerhard J. Woeginger:
An On-Line Scheduling Heuristic With Better Worst Case Ratio Than Graham's List Scheduling. 349-355 - Robert Cypher:
Theoretical Aspects of VLSI Pin Limitations. 356-378 - Shlomo Moran, Manfred K. Warmuth:
Gap Theorems for Distributed Computation. 379-394 - Ronald V. Book, Jack H. Lutz:
On Languages With Very High Space-Bounded Kolmogorov Complexity. 395-402 - Noga Alon, Moni Naor:
Coin-Flipping Games Immune Against Linear-Sized Coalitions. 403-417 - Herbert Edelsbrunner, Raimund Seidel, Micha Sharir:
On the Zone Theorem for Hyperplane Arrangements. 418-429
Volume 22, Number 3, June 1993
- Ming-Yang Kao:
Linear-Processor NC Algorithms for Planar Directed Graphs I: Strongly Connected Components. 431-459 - Ming-Yang Kao, Gregory E. Shannon:
Linear-Processor NC Algorithms for Planar Directed Graphs II: Directed Spanning Trees. 460-481 - Daniel Bienstock, Nicole Diaz:
Blocking Small Cuts in a Network, and Related Problems. 482-499 - Kok-Hoo Yeap, Majid Sarrafzadeh:
Floor-Planning by Graph Dualization: 2-Concave Rectilinear Modules. 500-526 - Herbert Edelsbrunner, Tiow Seng Tan:
A Quadratic Time Algorithm for the Minimax Length Triangulation. 527-551 - K. Kalorkoti:
Inverting Polynomials and Formal Power Series. 552-559 - Jonathan F. Buss, Judy Goldsmith:
Nondeterminism Within P. 560-572 - Lefteris M. Kirousis, Maria J. Serna, Paul G. Spirakis:
Parallel Complexity of the Connected Subgraph Problem. 573-586 - Donald S. Fussell, Vijaya Ramachandran, Ramakrishna Thurimella:
Finding Triconnected Components by Local Replacement. 587-616 - Dario Bini, Victor Y. Pan:
Improved Parallel Polynomial Division. 617-626 - Daniel J. Rosenkrantz, Harry B. Hunt III:
The Complexity of Processing Hierarchical Specifications. 627-649 - Edward G. Coffman Jr., Leopold Flatto, Paul E. Wright:
A Stochastic Checkpoint Optimization Problem. 650-659
Volume 22, Number 4, August 1993
- Andreas Goerdt:
Regular Resolution Versus Unrestricted Resolution. 661-683 - Harald Niederreiter, Claus-Peter Schnorr:
Local Randomness in Polynomial Random Number and Random Function Generators. 684-694 - Arne Dür, Johannes Grabmeier:
Applying Coding Theory to Sparse Interpolation. 695-704 - Sally A. Goldman, Michael J. Kearns, Robert E. Schapire:
Exact Identification of Read-Once Formulas Using Fixed Points of Amplification Functions. 705-726 - Louise E. Moser, P. M. Melliar-Smith, Vivek Agrawala:
Asynchronous Fault-Tolerant Total Ordering Algorithms. 727-750 - Arthur S. Goldstein, Edward M. Reingold:
A Fibonacci Version of Kraft's Inequality Applied to Discrete Unimodal Search. 751-777 - Pankaj K. Agarwal, Marco Pellegrini
Counting Circular Arc Intersections. 778-793 - Pankaj K. Agarwal, Jirí Matousek:
Ray Shooting and Parametric Search. 794-806 - Michael J. Kearns, Ming Li:
Learning in the Presence of Malicious Errors. 807-837 - Joseph Naor, Moni Naor:
Small-Bias Probability Spaces: Efficient Constructions and Applications. 838-856 - David Harel, Danny Raz:
Deciding Properties of Nonregular Programs. 857-874 - Reuven Bar-Yehuda, Amos Israeli, Alon Itai:
Multiple Communication in Multihop Radio Networks. 875-887
Volume 22, Number 5, October 1993
- Tsan-sheng Hsu, Vijaya Ramachandran:
Finding a Smallest Augmentation to Biconnect a Graph. 889-912 - Bernd Halstenberg, Rüdiger Reischuk:
Different Modes of Communication. 913-934 - Udi Manber, Eugene W. Myers:
Suffix Arrays: A New Method for On-Line String Searches. 935-948 - Andreas Blass, Yuri Gurevich:
Randomizing Reductions of Search Problems. 949-975 - Ruey-Der Lou, Majid Sarrafzadeh:
An Optimal Algorithm for the Maximum Three-Chain Problem. 976-993 - Joan Feigenbaum, Lance Fortnow:
Random-Self-Reducibility of Complete Sets. 994-1005 - Sally A. Goldman, Ronald L. Rivest, Robert E. Schapire:
Learning Binary Relations and Total Orders. 1006-1034 - Michael Formann, Torben Hagerup, James Haralambides, Michael Kaufmann, Frank Thomson Leighton, Antonios Symvonis
Drawing Graphs in the Plane with High Resolution. 1035-1052 - Béla Bollobás, István Simon:
Probabilistic Analysis of Disjoint Set Union Algorithms. 1053-1074 - Jack H. Lutz:
A Pseudorandom Oracle Characterization of BPP. 1075-1086 - Mark Jerrum, Alistair Sinclair:
Polynomial-Time Approximation Algorithms for the Ising Model. 1087-1116
Volume 22, Number 6, December 1993
- Tao Jiang
Minimal NFA Problems are Hard. 1117-1141 - Jiazhen Cai, Xiaofeng Han, Robert Endre Tarjan:
An O(m log n)-Time Algorithm for the Maximal Planar Subgraph Problem. 1142-1162 - Oded Goldreich
On the Existence of Pseudorandom Generators. 1163-1175 - Wojciech Szpankowski:
A Generalized Suffix Tree and its (Un)expected Asymptotic Behaviors. 1176-1198 - David R. Karger
Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths. 1199-1217 - Xin He:
On Finding the Rectangular Duals of Planar Triangular Graphs. 1218-1226 - Victor Y. Pan, John H. Reif:
Fast and Efficient Parallel Solution of Sparse Linear Systems. 1227-1250 - Wansoo T. Rhee, Michel Talagrand:
On-Line Bin Packing of Items of Random Sizes, II. 1251-1256 - Ricard Gavaldà
On the Computational Complexity of Small Descriptions. 1257-1275 - Marek Karpinski, Thorsten Werther:
VC Dimension and Uniform Learnability of Sparse Polynomials and Rational Functions. 1276-1285 - Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir, Jack Snoeyink:
Computing a Face in an Arrangement of Line Segments and Related Problems. 1286-1302 - Bo Chen
A Better Heuristic for Preemptive Parallel Machine Scheduling with Batch Setup Times. 1303-1318 - Jiang-Hsing Chu, Gary D. Knott:
A New Method for Computing Page-Fault Rates. 1319-1330 - Eyal Kushilevitz, Yishay Mansour:
Learning Decision Trees Using the Fourier Spectrum. 1331-1348 - Richard Cole:
Correction: Parallel Merge Sort. 1349
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-11-14 20:49 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: