@article{Sagiv/88,
AUTHOR = {Sagiv, Y.},
TITLE = {On bounded database schemes and bounded Horn-clause programs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
NUMBER = {1},
PAGES = {1-22},
YEAR = {1988, February},
PUBLISHER = {Society for Industrial and Applied Mathematics},
INSTITUTION = {Dept. of Comput. Sci., Hebrew Univ., Jerusalem, Israel},
ADDRESS = {Philadelphia, PA},
}
@article{Friesen-Kuhl/88,
AUTHOR = {Friesen, D.K. and Kuhl, F.S.},
TITLE = {Analysis of a hybrid algorithm for packing unequal bins},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
NUMBER = {1},
PAGES = {23-40},
YEAR = {1988, February},
PUBLISHER = {Society for Industrial and Applied Mathematics},
INSTITUTION = {MITRE Corp., Civil Syst. Div., McLean, VA, USA},
ADDRESS = {Philadelphia, PA},
}
@article{Masuda-Nakajima/88,
AUTHOR = {Masuda, S. and Nakajima, K.},
TITLE = {An optimal algorithm for finding a maximum independent set of a circular-arc graph},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
NUMBER = {1},
PAGES = {41-52},
YEAR = {1988, February},
PUBLISHER = {Society for Industrial and Applied Mathematics},
INSTITUTION = {Dept. of Electr. Eng., Maryland Univ., College Park, MD, USA},
ADDRESS = {Philadelphia, PA},
}
@article{Bienstock-Monma/88,
AUTHOR = {Bienstock, D. and Monma, C.L.},
TITLE = {On the complexity of covering vertices by faces in a planar graph},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
NUMBER = {1},
PAGES = {53-76},
YEAR = {1988, February},
PUBLISHER = {Society for Industrial and Applied Mathematics},
INSTITUTION = {Bell Commun. Res., Morristown, NJ, USA},
ADDRESS = {Philadelphia, PA},
}
@article{Katajainen-van_Leeuwen-Penttonen/88,
AUTHOR = {Katajainen, J. and van Leeuwen, Jan and Penttonen, M.},
TITLE = {Fast simulation of Turing machines by random access machines},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
NUMBER = {1},
PAGES = {77-88},
YEAR = {1988, February},
PUBLISHER = {Society for Industrial and Applied Mathematics},
INSTITUTION = {Dept. of Comput. Sci., Turku Univ., Finland;},
ADDRESS = {Philadelphia, PA},
}
@article{Fushimi/88,
AUTHOR = {Fushimi, M.},
TITLE = {Designing a uniform random number generator whose subsequences are $k$-distributed},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
NUMBER = {1},
PAGES = {89-99},
YEAR = {1988, February},
PUBLISHER = {Society for Industrial and Applied Mathematics},
INSTITUTION = {Dept. of Math. Eng. \& Instrum. Phys., Tokyo Univ., Japan},
ADDRESS = {Philadelphia, PA},
}
@article{Faigle-Turan/88,
AUTHOR = {Faigle, U. and Tur{\'a}n, G.},
TITLE = {Sorting and recognition problems for ordered sets},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
NUMBER = {1},
PAGES = {100-113},
YEAR = {1988, February},
PUBLISHER = {Society for Industrial and Applied Mathematics},
INSTITUTION = {Inst. f{\"u}r {\"o}konometrie und Oper. Res., Rheinische Friedrich-Wilhelms-Univ. Bonn, Germany},
ADDRESS = {Philadelphia, PA},
}
@article{Nicol/88,
AUTHOR = {Nicol, D.M.},
TITLE = {Expected performance of $m$-solution backtracking},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
NUMBER = {1},
PAGES = {114-127},
YEAR = {1988, February},
PUBLISHER = {Society for Industrial and Applied Mathematics},
INSTITUTION = {Inst. for Comput. Applications in Sci. \& Eng., NASA Langley Res. Center, Hampton, VA, USA},
ADDRESS = {Philadelphia, PA},
}
@article{Cole-Vishkin/88a,
AUTHOR = {Cole, R. and Vishkin, U.},
TITLE = {Approximate parallel scheduling. I. The basic technique with applications to optimal parallel list ranking in logarithmic time},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
NUMBER = {1},
PAGES = {128-142},
YEAR = {1988, February},
PUBLISHER = {Society for Industrial and Applied Mathematics},
INSTITUTION = {Courant Inst. of Math. Sci., New York Univ., NY, USA},
ADDRESS = {Philadelphia, PA},
}
@article{Tarjan-Wyk/88,
AUTHOR = {Tarjan, R.E. and Wyk, C.J. van},
TITLE = {An $O(n \log\log n)$-time algorithm for triangulating a simple polygon},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
NUMBER = {1},
PAGES = {143-178},
YEAR = {1988, February},
PUBLISHER = {Society for Industrial and Applied Mathematics},
INSTITUTION = {AT\&T Bell Labs., Murray Hill, NJ, USA},
ADDRESS = {Philadelphia, PA},
NOTE = {see Erratum in SIAM J. Comput., Vol. 17, 1061},
}
@article{Bach/88,
AUTHOR = {Bach, E.},
TITLE = {How to generate factored random numbers},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
NUMBER = {2},
PAGES = {179-193},
YEAR = {1988, April},
PUBLISHER = {Society for Industrial and Applied Mathematics},
INSTITUTION = {Dept. of Comput. Sci., Wisconsin Univ., WI, USA},
ADDRESS = {Philadelphia, PA},
}
@article{Alexi-Chor-Goldreich-Schnorr/88,
AUTHOR = {Alexi, W. and Chor, B. and Goldreich, O. and Schnorr, C.P.},
TITLE = {RSA and Rabin functions: certain parts are as hard as the whole},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
NUMBER = {2},
PAGES = {194-209},
YEAR = {1988, April},
PUBLISHER = {Society for Industrial and Applied Mathematics},
INSTITUTION = {Fachbereich Math., Univ. Frankfurt, Germany;},
ADDRESS = {Philadelphia, PA},
}
@article{Bennett-Brassard-Robert/88,
AUTHOR = {Bennett, C.H. and Brassard, G. and Robert, J.-M.},
TITLE = {Privacy amplification by public discussion},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
NUMBER = {2},
PAGES = {210-229},
YEAR = {1988, April},
PUBLISHER = {Society for Industrial and Applied Mathematics},
INSTITUTION = {IBM Thomas J. Watson Res. Lab., Yorktown Heights, NY, USA},
ADDRESS = {Philadelphia, PA},
}
@article{Chor-Goldreich/88,
AUTHOR = {Chor, B. and Goldreich, O.},
TITLE = {Unbiased bits from sources of weak randomness and probabilistic communication complexity},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
NUMBER = {2},
PAGES = {230-261},
YEAR = {1988, April},
PUBLISHER = {Society for Industrial and Applied Mathematics},
INSTITUTION = {MIT, Cambridge, MA, USA},
ADDRESS = {Philadelphia, PA},
}
@article{Frieze-Hastad-Kannan-Lagarias-Shamir/88,
AUTHOR = {Frieze, A.M. and H{\aa}stad, J. and Kannan, R. and Lagarias, J.C. and Shamir, A.},
TITLE = {Reconstructing truncated integer variables satisfying linear congruences},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
NUMBER = {2},
PAGES = {262-280},
YEAR = {1988, April},
PUBLISHER = {Society for Industrial and Applied Mathematics},
INSTITUTION = {Carnegie-Mellon Univ., Pittsburgh, PA, USA},
ADDRESS = {Philadelphia, PA},
}
@article{Goldwasser-Micali-Rivest/88,
AUTHOR = {Goldwasser, S. and Micali, S. and Rivest, R.L.},
TITLE = {A digital signature scheme secure against adaptive chosen-message attacks},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
NUMBER = {2},
PAGES = {281-308},
YEAR = {1988, April},
PUBLISHER = {Society for Industrial and Applied Mathematics},
INSTITUTION = {Lab. for Comput. Sci., MIT, Cambridge, MA, USA},
ADDRESS = {Philadelphia, PA},
}
@article{Grollmann-Selman/88,
AUTHOR = {Grollmann, J. and Selman, A.L.},
TITLE = {Complexity measures for public-key cryptosystems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
NUMBER = {2},
PAGES = {309-335},
YEAR = {1988, April},
PUBLISHER = {Society for Industrial and Applied Mathematics},
INSTITUTION = {Siemens AG, Munich, Germany},
ADDRESS = {Philadelphia, PA},
}
@article{Hastad/88a,
AUTHOR = {H{\aa}stad, J.},
TITLE = {Solving simultaneous modular equations of low degree},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
NUMBER = {2},
PAGES = {336-341},
YEAR = {1988, April},
PUBLISHER = {Society for Industrial and Applied Mathematics},
INSTITUTION = {Lab. for Comput. Sci., MIT, Cambridge, MA, USA},
ADDRESS = {Philadelphia, PA},
}
@article{Lagarias-Reeds/88,
AUTHOR = {Lagarias, J.C. and Reeds, J.A.},
TITLE = {Unique extrapolation of polynomial recurrences},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
NUMBER = {2},
PAGES = {342-362},
YEAR = {1988, April},
PUBLISHER = {Society for Industrial and Applied Mathematics},
INSTITUTION = {AT\&T Bell Labs., Murray Hill, NJ, USA},
ADDRESS = {Philadelphia, PA},
}
@article{Long-Wigderson/88,
AUTHOR = {Long, D.L. and Wigderson, A.},
TITLE = {The discrete logarithm hides $O(\log n)$ bits},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
NUMBER = {2},
PAGES = {363-372},
YEAR = {1988, April},
PUBLISHER = {Society for Industrial and Applied Mathematics},
INSTITUTION = {Dept. of Comput. Sci., Wellesley Coll., MA, USA},
ADDRESS = {Philadelphia, PA},
}
@article{Luby-Rackoff/88,
AUTHOR = {Luby, M. and Rackoff, C.},
TITLE = {How to construct pseudorandom permutations from pseudorandom functions},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
NUMBER = {2},
PAGES = {373-386},
YEAR = {1988, April},
PUBLISHER = {Society for Industrial and Applied Mathematics},
INSTITUTION = {Dept. of Comput. Sci., Toronto Univ., Ont., Canada},
ADDRESS = {Philadelphia, PA},
}
@article{Pomerance-Smith-Tuler/88,
AUTHOR = {Pomerance, C. and Smith, J.W. and Tuler, R.},
TITLE = {A pipeline architecture for factoring large integers with the quadratic sieve algorithm},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
NUMBER = {2},
PAGES = {387-403},
YEAR = {1988, April},
PUBLISHER = {Society for Industrial and Applied Mathematics},
INSTITUTION = {Dept. of Math., Georgia Univ., Athens, GA, USA},
ADDRESS = {Philadelphia, PA},
}
@article{Reif-Tygar/88,
AUTHOR = {Reif, J.H. and Tygar, J.D.},
TITLE = {Efficient parallel pseudorandom number generation},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
NUMBER = {2},
PAGES = {404-411},
YEAR = {1988, April},
PUBLISHER = {Society for Industrial and Applied Mathematics},
INSTITUTION = {Lab. for Comput. Sci., MIT, MA, USA},
ADDRESS = {Philadelphia, PA},
}
@article{Micali-Rackoff-Sloan/88,
AUTHOR = {Micali, S. and Rackoff, C. and Sloan, B.},
TITLE = {The notion of security for probabilistic cryptosystems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
NUMBER = {2},
PAGES = {412-426},
YEAR = {1988, April},
PUBLISHER = {Society for Industrial and Applied Mathematics},
INSTITUTION = {Lab. for Comput. Sci., MIT, Cambridge, MA, USA},
ADDRESS = {Philadelphia, PA},
}
@article{Chazelle/88a,
AUTHOR = {Chazelle, Bernard},
TITLE = {A functional approach to data structures and its use in multidimensional searching},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {427-462},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Klein-Reif/88,
AUTHOR = {Klein, Philip N. and Reif, John H.},
TITLE = {Parallel time $O(\log n)$ acceptance of deterministic CFLs on an exclusive-write P-RAM},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {463-485},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{He-Yesha/88a,
AUTHOR = {He, Xin and Yesha, Yaacov},
TITLE = {A nearly optimal parallel algorithm for constructing depth first spanning trees in planar graphs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {486-491},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Pittel-Yu/88,
AUTHOR = {Pittel, Boris and Yu, Jenn-Hwa},
TITLE = {On search times for early-insertion coalesced hashing},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {492-503},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Book-Orponen-Russo-Watanabe/88,
AUTHOR = {Book, R. and Orponen, P. and Russo, D. and Watanabe, O.},
TITLE = {Lowness properties of sets in the exponential-time hierarchy},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {504-516},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Yao/88,
AUTHOR = {Yao, Andrew Chi-Chih},
TITLE = {Monotone bipartite graph properties are evasive},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {517-520},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{dAtri-Moscarini/88a,
AUTHOR = {d'Atri, Alessandro and Moscarini, Marina},
TITLE = {Distance-hereditary graphs, Steiner trees, and connected domination},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {521-538},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Hochbaum-Shmoys/88,
AUTHOR = {Hochbaum, Dorit S. and Shmoys, David B.},
TITLE = {A polynomial approximation scheme for scheduling on uniform processors: Using the dual approximation approach},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {539-551},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Gusfield/88,
AUTHOR = {Gusfield, Dan},
TITLE = {A graph theoretic approach to statistical data security},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {552-571},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Vaidya/88,
AUTHOR = {Vaidya, Pravin M.},
TITLE = {Minimum spanning trees in $k$-dimensional space},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {572-582},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Siegel-Dolev/88,
AUTHOR = {Siegel, Alan and Dolev, Danny},
TITLE = {Some geometry for general river routing},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {583-605},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Fich-Ragde-Wigderson/88a,
AUTHOR = {Fich, Faith E. and Ragde, Prabhakar and Wigderson, Avi},
TITLE = {Relations between concurrent-write models of parallel computation},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {606-627},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Dershowitz-Marcus-Tarlecki/88,
AUTHOR = {Dershowitz, Nachum and Marcus, Leo and Tarlecki, Andrzej},
TITLE = {Existene, uniqueness, and construction of rewrite systems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {629-639},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{John/88,
AUTHOR = {John, John Welliaveetil},
TITLE = {A new lower bound for the set-partitioning problem},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {640-647},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Schaback/88,
AUTHOR = {Schaback, R.},
TITLE = {On the expected sublinearity of the Boyer-Moore algorithm},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {648-658},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Vitanyi/88a,
AUTHOR = {Vit{\'a}nyi, Paul M.B.},
TITLE = {Locality, communication, and interconnect length in multicomputers},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {659-672},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kucera/88,
AUTHOR = {Ku{\v{c}}era, Lud{\v{e}}k},
TITLE = {Isomorphism testing of unary algebras},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {673-686},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Miller-Ramachandran-Kaltofen/88,
AUTHOR = {Miller, Gary L. and Ramachandran, Vijaya and Kaltofen, Erich},
TITLE = {Efficient parallel evaluation of straight-line code and arithmetic circuits},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {687-695},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Ravi-Lloyd/88,
AUTHOR = {Ravi, S.S. and Lloyd, Errol L.},
TITLE = {The complexity of near-optimal programmable logic array folding},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {696-710},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Dwork-Kanellakis-Stockmeyer/88,
AUTHOR = {Dwork, Cynthia and Kanellakis, Paris C. and Stockmeyer, Larry},
TITLE = {Parallel algorithms for term matching},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {711-731},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Avis-Lai/88,
AUTHOR = {Avis, David and Lai, C.W.},
TITLE = {The probabilistic analysis of a heuristic for the assignment problem},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {732-741},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Gusfield/88a,
AUTHOR = {Gusfield, Dan},
TITLE = {The structure of the stable roommate problem: Efficient representation and enumeration of all stable assignments},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {742-769},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Cole/88a,
AUTHOR = {Cole, Richard},
TITLE = {Parallel merge sort},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {770-785},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
NOTE = {see Correction in SIAM J. Comput.\ 22, 1349},
}
@article{Grandjean/88,
AUTHOR = {Grandjean, Etienne},
TITLE = {A natural $NP$-complete problem with a nontrivial lower bound},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {786-809},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Gabow/88,
AUTHOR = {Gabow, Harold N.},
TITLE = {Scheduling UET systems on two uniform processors and length two pipelines},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {810-829},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Clarkson/88a,
AUTHOR = {Clarkson, Kenneth L.},
TITLE = {A randomized algorithm for closest-point queries},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {830-847},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Atallah-Kosaraju/88,
AUTHOR = {Atallah, Mikhail J. and Kosaraju, S. Rao},
TITLE = {Efficient solutions to some transportation problems with applications to minimizing robot arm travel},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {849-869},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Edelsbrunner-Skiena/88,
AUTHOR = {Edelsbrunner, Herbert and Skiena, Steven S.},
TITLE = {Probing convex polygons with X-rays},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {870-882},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Karp-Motwani-Raghavan/88,
AUTHOR = {Karp, Richard M. and Motwani, Rajeev and Raghavan, Prabhakar},
TITLE = {Deferred data structuring},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {883-902},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Book-Ko/88,
AUTHOR = {Book, Ronald V. and Ko, Ker-I},
TITLE = {On sets truth-table reducible to sparse sets},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {903-919},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Provan/88,
AUTHOR = {Provan, J. Scott},
TITLE = {An approximation scheme for finding Steiner trees with obstacles},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {920-934},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Immerman/88a,
AUTHOR = {Immerman, Neil},
TITLE = {Nondeterministic space is closed under complementation},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {935-938},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bloom-Esik/88,
AUTHOR = {Bloom, Stephen L. and Esik, Zoltan},
TITLE = {Varieties of iteration theories},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {939-966},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Dyer-Frieze/88,
AUTHOR = {Dyer, M.E. and Frieze, A.M.},
TITLE = {On the complexity of computing the volume of a polyhedron},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {967-974},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Dwork-Peleg-Pippenger-Upfal/88,
AUTHOR = {Dwork, Cynthia and Peleg, David and Pippenger, Nicholas and Upfal, Eli},
TITLE = {Fault tolerance in networks of bounded degree},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {975-988},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Selman/88a,
AUTHOR = {Selman, Alan L.},
TITLE = {Natural self-reducible sets},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {989-996},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Hennessy/88,
AUTHOR = {Hennessy, Matthew},
TITLE = {Axiomatising finite concurrent processes},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {997-1017},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Miller/88,
AUTHOR = {Miller, Zevi},
TITLE = {A linear algorithm for topological bandwidth in degree-three trees},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {1018-1035},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Zellini/88,
AUTHOR = {Zellini, Paolo},
TITLE = {Optimal bounds for solving tridiagonal systems with preconditioning},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {1036-1043},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{McDiarmid/88,
AUTHOR = {McDiarmid, Colin},
TITLE = {Average-case lower bounds for searching},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {1044-1060},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Lengauer-Wanke/88a,
AUTHOR = {Lengauer, Thomas and Wanke, Egon},
TITLE = {Efficient solution of connectivity problems on hierarchically defined graphs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {1063-1080},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Ben-Or-Feig-Kozen-Tiwari/88,
AUTHOR = {Ben-Or, Michael and Feig, Ephraim and Kozen, Dexter and Tiwari, Prasoon},
TITLE = {A fast parallel algorithm for determining all roots of a polynomial with real roots},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {1081-1092},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Mehlhorn-Naher-Alt/88,
AUTHOR = {Mehlhorn, Kurt and N{\"a}her, Stefan and Alt, Helmut},
TITLE = {A lower bound on the complexity of the union-split-find problem},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {1093-1102},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Morris-Wong/88,
AUTHOR = {Morris, Robert J.T. and Wong, Wing Swing},
TITLE = {A short-term neural network memory},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {1103-1118},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bollobas-Brightwell/88,
AUTHOR = {Bollob{\'a}s, B{\'e}la and Brightwell, Graham},
TITLE = {Transitive orientations of graph},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {1119-1133},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bergstra-Klop-Olderog/88,
AUTHOR = {Bergstra, J.A. and Klop, J.W. and Olderog, E.-R.},
TITLE = {Readies and failures in the algebra of communicating processes},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {1134-1177},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Alon-Azar/88,
AUTHOR = {Alon, N. and Azar, Y.},
TITLE = {The average complexity of deterministic and randomized parallel comparison-sorting algorithms},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {1178-1192},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Allender-Rubinstein/88,
AUTHOR = {Allender, Eric W. and Rubinstein, Roy S.},
TITLE = {P-printable sets},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {1193-1202},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Knight/88,
AUTHOR = {Knight, William J.},
TITLE = {Search in an ordered array having variable probe cost},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {1203-1214},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kong-Mount-Roscoe/88,
AUTHOR = {Kong, T.Y. and Mount, David M. and Roscoe, A.W.},
TITLE = {The decomposition of a rectangle into rectangles of minimal perimeter},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {1215-1231},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Cai-Gundermann-Hartmanis-Hemachandra-Sewelson-Wagner-Wechsung/88,
AUTHOR = {Cai, Jin-Yi and Gundermann, Thomas and Hartmanis, Juris and Hemachandra, Lane A. and Sewelson, Vivian and Wagner, Klaus and Wechsung, Gerd},
TITLE = {The Boolean hierarchy I: Structural properties},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {1232-1252},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Schieber-Vishkin/88,
AUTHOR = {Schieber, Baruch and Vishkin, Uzi},
TITLE = {On finding lowest common ancestors: Simplification and parallelization},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {1253-1262},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Kadin/88a,
AUTHOR = {Kadin, Jim},
TITLE = {The polynomial time hierarchy collapses if the Boolean hierarchy collapses},
JOURNAL = {SIAM J. Comput.},
VOLUME = {17},
PAGES = {1263-1282},
YEAR = {1988},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
NOTE = {see Erratum in SIAM J. Comput., Vol. 20, 404},
}