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
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
Copyright © Tue Feb 9 19:48:09 2010
by Michael Ley (ley@uni-trier.de)
