SIAM Journal on Computing, Volume 28
Volume 28, Number 1, 1998
Haripriyan Hampapuram, Michael L. Fredman: Optimal Biweighted Binary Trees and the Complexity of Maintaining Partial Sums. 1-9- Marius Zimand: Weighted NP Optimization Problems: Logical Definability and Approximation Properties. 36-56
- Tomás Feder, Moshe Y. Vardi: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory. 57-104
- Thomas H. Cormen, Thomas Sundquist, Leonard F. Wisniewski: Asymptotically Tight Bounds for Performing BMMC Permutations on Parallel Disk Systems. 105-136
- Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani: On Syntactic versus Computational Views of Approximability. 164-191
- Stefan Felsner, Lorenz Wernisch: Maximum k-Chains in Planar Point Sets: Combinatorial Structure and Algorithms. 192-209
- Edith Cohen: Fast Algorithms for Constructing t-Spanners and Paths with Stretch t. 210-236
- Uwe Schwiegelshohn, Walter Ludwig, Joel L. Wolf, John Turek, Philip S. Yu: Smart SMART Bounds for Weighted Response Time Scheduling. 237-253
- Baruch Awerbuch, Yossi Azar, Avrim Blum, Santosh Vempala: New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen. 254-262
- Baruch Awerbuch, Bonnie Berger, Lenore Cowen, David Peleg: Near-Linear Time Construction of Sparse Neighborhood Covers. 263-277
- David Avis, Bryan Beresford-Smith, Luc Devroye, Hossam A. ElGindy, Eric Guévremont, Ferran Hurtado, Binhai Zhu: Unoriented Theta-Maxima in the Plane: Complexity and Algorithms. 278-296
- Jonathan E. Atkins, Erik G. Boman, Bruce Hendrickson: A Spectral Algorithm for Seriation and the Consecutive Ones Problem. 297-310
- Viliam Geffert, Carlo Mereghetti, Giovanni Pighizzini: Sublogarithmic Bounds on Space and Reversals. 325-340
- David Eppstein, Zvi Galil, Giuseppe F. Italiano, Thomas H. Spencer: Separator-Based Sparsification II: Edge and Vertex Connectivity. 341-381
Volume 28, Number 2, 1998
- Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel: A Downward Collapse within the Polynomial Hierarchy. 383-393
- Yongge Wang: Genericity, Randomness, and Polynomial-Time Approximations. 394-408
- Luc Devroye: Universal Limit Laws for Depths in Random Trees. 409-432
- William S. Evans, Nicholas Pippenger: Average-Case Lower Bounds for Noisy Boolean Decision Trees. 433-446
- Amos Fiat, Dean P. Foster, Howard J. Karloff, Yuval Rabani, Yiftach Ravid, Sundar Vishwanathan: Competitive Algorithms for Layered Graph Traversal. 447-462
- Francis Y. L. Chin, Cao An Wang: Finding the Constrained Delaunay Triangulation and Constrained Voronoi Diagram of a Simple Polygon in Linear Time. 471-486
- Sigal Ar, Richard J. Lipton, Ronitt Rubinfeld, Madhu Sudan: Reconstructing Algebraic Functions from Mixed Data. 487-510
- Baruch Awerbuch, Israel Cidon, Shay Kutten, Yishay Mansour, David Peleg: Optimal Broadcast with Partial Knowledge. 511-524
- Sridhar Rajagopalan, Vijay V. Vazirani: Primal-Dual RNC Approximation Algorithms for Set Cover and Covering Integer Programs. 525-540
- Andrei Z. Broder, Alan M. Frieze, Stephen Suen, Eli Upfal: Optimal Construction of Edge-Disjoint Paths in Random Graphs. 541-573
- Zoran Ivkovic, Errol L. Lloyd: Fully Dynamic Algorithms for Bin Packing: Being (Mostly) Myopic Helps. 574-611
- David Eppstein: Finding the k Shortest Paths. 652-673
- Nader H. Bshouty, Paul W. Goldberg, Sally A. Goldman, H. David Mathias: Exact Learning of Discretized Geometric Concepts. 674-699
- Yacov Yacobi: Fast Exponentiation Using Data Compression. 700-703
- P. G. Walsh: A Polynomial Time Complexity Bound for Computations on Curves. 704-708
- Phillip B. Gibbons, Yossi Matias, Vijaya Ramachandran: The Queue-Read Queue-Write PRAM Model: Accounting for Contention in Parallel Algorithms. 733-769
Volume 28, Number 3, 1998
- Joseph S. B. Mitchell, Avrim Blum, Prasad Chalasani, Santosh Vempala: A Constant-Factor Approximation Algorithm for the Geometric k-MST Problem in the Plane. 771-781
- Prasad Jayanti: Solvability of Consensus: Composition Breaks Down for NonDeterministic Types. 782-797
- Stephen Ponzio: A Lower Bound for Integer Multiplication with Read-Once Branching Programs. 798-815
- Joachim von zur Gathen, Igor Shparlinski: Computing components and projections of curves over finite fields. 822-840
- Alexander Schrijver: Bipartite Edge Coloring in O(Delta m) Time. 841-846
- Jop F. Sibeyn: Row-Major Sorting on Meshes. 847-863
- Giuseppe Liotta, Franco P. Preparata, Roberto Tamassia: Robust Proximity Queries: An Illustration of Degree-Driven Algorithm Design. 864-889
- Marcos Kawazoe Aguilera, Sam Toueg: Failure Detection and Randomization: A Hybrid Approach to Solve Consensus. 890-903
Volume 28, Number 3, 1999
- Guy Louchard, Wojciech Szpankowski, Jing Tang: Average Profile of the Generalized Digital Search Tree and the Generalized Lempel-Ziv Algorithm. 904-934
- Ming-Yang Kao, Junfeng Qi, Lei Tan: Optimal Bidding Algorithms Against Cheating in Multiple-Object Auctions. 955-969
- Bruce M. Maggs, Ramesh K. Sitaraman: Simple Algorithms for Routing on Butterfly Networks with Bounded Queues. 984-1003
- Wen-Lian Hsu, Tze-Heng Ma: Fast and Simple Algorithms for Recognizing Chordal Comparability Graphs and Interval Graphs. 1004-1020
- David R. Karger, Noam Nisan, Michal Parnas: Fast Connected Components Algorithms for the EREW PRAM. 1021-1034
- Paul Beame, Allan Borodin, Prabhakar Raghavan, Walter L. Ruzzo, Martin Tompa: A Time-Space Tradeoff for Undirected Graph Traversal by Walking Automata. 1051-1072
- Richa Agarwala, Vineet Bafna, Martin Farach, Mike Paterson, Mikkel Thorup: On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics). 1073-1085
- Carsten Lund, Nick Reingold, Jeffery Westbrook, Dicky C. K. Yan: Competitive On-Line Algorithms for Distributed Data Management. 1086-1111
- Nader H. Bshouty, Jeffrey C. Jackson: Learning DNF over the Uniform Distribution Using a Quantum Example Oracle. 1136-1153
Volume 28, Number 4, 1999
- Hans Kellerer, Thomas Tautenhahn, Gerhard J. Woeginger: Approximability and Nonapproximability Results for Minimizing Total Flow Time on a Single Machine. 1155-1166
- Donald Aingworth, Chandra Chekuri, Piotr Indyk, Rajeev Motwani: Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication). 1167-1181
- Sariel Har-Peled: Constructing Approximate Shortest Path Maps in Three Dimensions. 1182-1197
- Jeff Erickson: New Lower Bounds for Convex Hull Problems in Odd Dimensions. 1198-1214
- Luc Devroye: The Height and Size of Random Hash Trees and Random Pebbled Hash Trees. 1215-1224
- Guo-Hui Lin, Ding-Zhu Du, Xiao-Dong Hu, Guoliang Xue: On Rearrangeability of Multirate Clos Networks. 1225-1231
- Prasad Tetali: Design of On-Line Algorithms Using Hitting Times. 1232-1246
- Edward G. Thurber: Efficient Generation of Minimal Length Addition Chains. 1247-1263
- Jie Wang: Distributional Word Problem for Groups. 1264-1283
- Derek G. Corneil, Stephan Olariu, Lorna Stewart: Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs. 1284-1297
- Joseph S. B. Mitchell: Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems. 1298-1309
- Boris V. Cherkassky, Andrew V. Goldberg, Craig Silverstein: Buckets, Heaps, Lists, and Monotone Priority Queues. 1326-1346
- Ichiro Suzuki, Masafumi Yamashita: Distributed Anonymous Mobile Robots: Formation of Geometric Patterns. 1347-1363
- Johan Håstad, Russell Impagliazzo, Leonid A. Levin, Michael Luby: A Pseudorandom Generator from any One-way Function. 1364-1396
- Hagit Attiya, Hadas Shachnai, Tami Tamir: Local Labeling and Resource Allocation Using Preprocessing. 1397-1414
- Harry Buhrman, Jaap-Henk Hoepman, Paul M. B. Vitányi: Space-efficient Routing Tables for Almost All Networks and the Incompressibility Method. 1414-1432
- Ketan Mulmuley: Lower Bounds in a Parallel Model without Bit Operations. 1460-1509
- Lenwood S. Heath, Sriram V. Pemmaraju, Ann N. Trenk: Stack and Queue Layouts of Directed Acyclic Graphs: Part I. 1510-1539
Volume 28, Number 5, 1999
- Weiping Shi, Douglas B. West: Diagnosis of Wiring Networks: An Optimal Randomized Algorithm for Finding Connected Components of Unknown Graphs. 1541-1551
- Hervé Brönnimann, Bernard Chazelle, Jirí Matousek: Product Range Spaces, Sensitive Sampling, and Derandomization. 1552-1575
- Lenwood S. Heath, Sriram V. Pemmaraju: Stack and Queue Layouts of Directed Acyclic Graphs: Part II. 1588-1626
- Sanjeev Mahajan, H. Ramesh: Derandomizing Approximation Algorithms Based on Semidefinite Programming. 1641-1663
- Gary L. Miller, Shang-Hua Teng: The Dynamic Parallel Complexity of Computational Circuits. 1664-1688
- Ueli M. Maurer, Stefan Wolf: The Relationship Between Breaking the Diffie-Hellman Protocol and Computing Discrete Logarithms. 1689-1721
- Pierluigi Crescenzi, Viggo Kann, Riccardo Silvestri, Luca Trevisan: Structure in Approximation Classes. 1759-1782
- Amotz Bar-Noy, Ran Canetti, Shay Kutten, Yishay Mansour, Baruch Schieber: Bandwidth Allocation with Preemption. 1806-1828
- Douglas Stott Parker Jr., Prasad Ram: The Construction of Huffman Codes is a Submodular ("Convex") Optimization Problem Over a Lattice of Binary Trees. 1875-1905
- Haim Kaplan, Ron Shamir, Robert Endre Tarjan: Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs. 1906-1922
Volume 28, Number 6, 1999
- Richard J. Anderson: Tree Data Structures for N-Body Simulation. 1923-1940
- John Case: The Power of Vacillation in Language Learning. 1941-1969
- Andries E. Brouwer: An Associative Block Design ABD(8, 5). 1970-1971
- Ronitt Rubinfeld: On the Robustness of Functional Equations. 1972-1997
- Barun Chandra, Howard J. Karloff, Craig A. Tovey: New Results on the Old k-opt Algorithm for the Traveling Salesman Problem. 1998-2029
- Mauro Leoncini, Giovanni Manzini, Luciano Margara: Parallel Complexity of Numerically Accurate Linear System Solvers. 2030-2058
- John H. Reif: Approximate Complex Polynomial Evaluation in Near Constant Work Per Point. 2059-2089
- Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim, Luca Trevisan: Weak Random Sources, Hitting Sets, and BPP Simulations. 2103-2116
- Prasad Chalasani, Rajeev Motwani: Approximating Capacitated Routing and Delivery Problems. 2133-2149
- Xin He: On Floor-Plan of Plane Graphs. 2150-2167
- Kazuhisa Makino, Ken'ichi Hatanaka, Toshihide Ibaraki: Horn Extensions of a Partially Defined Boolean Function. 2168-2186
- Guy Even, Joseph Naor, Satish Rao, Baruch Schieber: Fast Approximate Graph Partitioning Algorithms. 2187-2214
- John Hershberger, Subhash Suri: An Optimal Algorithm for Euclidean Shortest Paths in the Plane. 2215-2256
- Jeff Edmonds, Chung Keung Poon, Dimitris Achlioptas: Tight Lower Bounds for st-Connectivity on the NNJAG Model. 2257-2284
- Warwick Harvey: Computing Two-Dimensional Integer Hulls. 2285-2299
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-19T203413 by the dblp team