default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDSIAM 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 R. 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 S. 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 S. 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 E. 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 R. 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
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 2026-01-30 23:00 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:
