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
  
• Johannes A. La Poutré, Jeffery Westbrook:
  Dynamic 2-Connectivity with Backtracking. 10-26
  
• Gregorio Malajovich, Klaus Meer:
  On the Structure of NP_C. 27-35
  
• 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
  
• Lance Fortnow, Judy Goldsmith, Matthew A. Levy, Stephen R. Mahaney:
  L-Printable Sets. 137-151
  
• Dimitris J. Kavvadias, Martha Sideri:
  The Inverse Satisfiability Problem. 152-163
  
• 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
  
• Johannes Köbler, Osamu Watanabe:
  New Collapse Consequences of NP Having Small Circuits. 311-324
  
• 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
  
• Ding-Zhu Du, Biao Gao, Frank K. Hwang, J. H. Kim:
  On Multirate Rearrangeable Clos Networks. 463-470
  
• 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
  
• Michael T. Goodrich, Roberto Tamassia:
  Dynamic Trees and Dynamic Point Location. 612-636
  
• Lane A. Hemaspaandra, Harald Hempel, Gerd Wechsung:
  Query Order. 637-651
  
• 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
  
• Prabhakar Raghavan, Eli Upfal:
  Stochastic Contention Resolution With Short Delays. 709-719
  
• Lisa Higham, Teresa M. Przytycka:
  Asymptotically Optimal Election on Weighted Rings. 720-732
  
• 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
  
• Hugh Hind, Michael Molloy, Bruce A. Reed:
  Total Coloring With Delta + (log Delta) Colors. 816-821
  
• 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
  
• Chi-Chang Chen, Jianer Chen:
  The Maximum Partition Matching Problem with Applications. 935-954
  
• Ming-Yang Kao, Junfeng Qi, Lei Tan:
  Optimal Bidding Algorithms Against Cheating in Multiple-Object Auctions. 955-969
  
• Eli Gafni, Elias Koutsoupias:
  Three-Processor Tasks Are Undecidable. 970-983
  
• 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
  
• Noam Nisan, Steven Rudich, Michael E. Saks:
  Products and Help Bits in Decision Trees. 1035-1050
  
• 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
  
• Riccardo Torlone, Paolo Atzeni:
  Efficient Database Updates with Independent Schemes. 1112-1135
  
• 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
  
• Jin-yi Cai, Alan L. Selman:
  Fine Separation of Average-Time Complexity Classes. 1310-1325
  
• 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
  
• Aravind Srinivasan, David Zuckerman:
  Computing with Very Weak Random Sources. 1433-1459
  
• 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
  
• Aart J. C. Bik, Harry A. G. Wijshoff:
  Automatic Nonzero Structure Analysis. 1576-1587
  
• Lenwood S. Heath, Sriram V. Pemmaraju:
  Stack and Queue Layouts of Directed Acyclic Graphs: Part II. 1588-1626
  
• Andrej Brodnik, J. Ian Munro:
  Membership in Constant Time and Almost-Minimum Space. 1627-1640
  
• 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
  
• Dorit Dor, Uri Zwick:
  Selecting the Median. 1722-1758
  
• Pierluigi Crescenzi, Viggo Kann, Riccardo Silvestri, Luca Trevisan:
  Structure in Approximation Classes. 1759-1782
  
• Maurizio Talamo, Paola Vocca:
  An Efficient Data Structure for Lattice Operations. 1783-1805
  
• Amotz Bar-Noy, Ran Canetti, Shay Kutten, Yishay Mansour, Baruch Schieber:
  Bandwidth Allocation with Preemption. 1806-1828
  
• Leslie Ann Goldberg, Yossi Matias, Satish Rao:
  An Optical Simulation of Shared Memory. 1829-1847
  
• Cynthia Dwork, Maurice Herlihy, Serge A. Plotkin, Orli Waarts:
  Time-Lapse Snapshots. 1848-1874
  
• 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
  
• Yosi Ben-Asher, Eitan Farchi, Ilan Newman:
  Optimal Search in Trees. 2090-2102
  
• Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim, Luca Trevisan:
  Weak Random Sources, Hitting Sets, and BPP Simulations. 2103-2116
  
• Stephen Alstrup, Dov Harel, Peter W. Lauridsen, Mikkel Thorup:
  Dominators in Linear Time. 2117-2132
  
• 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
  

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