@article{Westbrook-Tarjan/89,
AUTHOR = {Westbrook, Jeffrey and Tarjan, Robert E.},
TITLE = {Amortized analysis of algorithms for set union with backtracking},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
NUMBER = {1},
PAGES = {1-11},
YEAR = {1989, February},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Abrahamson-Adler-Gelbart-Higham-Kirkpatrick/89,
AUTHOR = {Abrahamson, Karl and Adler, Andrew and Gelbart, Rachel and Higham, Lisa and Kirkpatrick, David},
TITLE = {The bit complexity of randomized leader election on a ring},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
NUMBER = {1},
PAGES = {12-29},
YEAR = {1989, February},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Gallo-Grigoriadis-Tarjan/89,
AUTHOR = {Gallo, Giorgio and Grigoriadis, Michael D. and Tarjan, Robert E.},
TITLE = {A fast parametric maximum flow algorithm and applications},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
NUMBER = {1},
PAGES = {30-55},
YEAR = {1989, February},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Wilber/89,
AUTHOR = {Wilber, Robert},
TITLE = {Lower bounds for accessing binary search trees with rotations},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
NUMBER = {1},
PAGES = {56-67},
YEAR = {1989, February},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Korte-Mohring/89,
AUTHOR = {Korte, Norbert and M{\"o}hring, Rolf H.},
TITLE = {An incremental linear-time algorithm for recognizing interval graphs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
NUMBER = {1},
PAGES = {68-81},
YEAR = {1989, February},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Larmore/89,
AUTHOR = {Larmore, Lawrence L.},
TITLE = {Minimum delay codes},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
NUMBER = {1},
PAGES = {82-94},
YEAR = {1989, February},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Cai-Gundermann-Hartmanis-Hemachandra-Sewelson-Wagner-Wechsung/89,
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 II: Applications},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
NUMBER = {1},
PAGES = {95-111},
YEAR = {1989, February},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Frederickson-Srinivas/89,
AUTHOR = {Frederickson, Greg N. and Srinivas, Mandayam A.},
TITLE = {Algorithms and data structures for an expanded family of matroid intersection problems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
NUMBER = {1},
PAGES = {112-138},
YEAR = {1989, February},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Rhee-Talagrand/89c,
AUTHOR = {Rhee, Wansoo T. and Talagrand, Michel},
TITLE = {Optimal bin packing with items of random sizes II},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
NUMBER = {1},
PAGES = {139-151},
YEAR = {1989, February},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Ordman/89,
AUTHOR = {Ordman, Edward T.},
TITLE = {Minimal threshold separators and memory requirements for synchronization},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
NUMBER = {1},
PAGES = {152-165},
YEAR = {1989, February},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Coffman-Lagarias/89,
AUTHOR = {Coffman, E.G., Jr. and Lagarias, J.C.},
TITLE = {Algorithms for packing squares: A probabilistic analysis},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
NUMBER = {1},
PAGES = {166-185},
YEAR = {1989, February},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Goldwasser-Micali-Rackoff/89,
AUTHOR = {Goldwasser, Shafi and Micali, Silvio and Rackoff, Charles},
TITLE = {The knowledge complexity of interactive proof systems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
NUMBER = {1},
PAGES = {186-208},
YEAR = {1989, February},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Lickteig/89,
AUTHOR = {Lickteig, Thomas},
TITLE = {A lower bound on the complexity of division in finite extension fields and inversion in quadratic alternative algebras},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
NUMBER = {2},
PAGES = {209-215},
YEAR = {1989, April},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bilardi-Nicolau/89,
AUTHOR = {Bilardi, Gianfranco and Nicolau, Alexandru},
TITLE = {Adaptive bitonic sorting: An optimal parallel algorithm for shared-memory machines},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
NUMBER = {2},
PAGES = {216-228},
YEAR = {1989, April},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Peleg-Upfal/89b,
AUTHOR = {Peleg, David and Upfal, Eli},
TITLE = {The token distribution problem},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
NUMBER = {2},
PAGES = {229-243},
YEAR = {1989, April},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Hwang-Chow-Anger-Lee/89,
AUTHOR = {Hwang, Jing-Jang and Chow, Yuan-Chieh and Anger, Frank D. and Lee, Chung-Yee},
TITLE = {Scheduling precedence graphs in systems with interprocessor communication times},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
NUMBER = {2},
PAGES = {244-257},
YEAR = {1989, April},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Alon-Azar/89,
AUTHOR = {Alon, N. and Azar, Y.},
TITLE = {Finding an approximate maximum},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
NUMBER = {2},
PAGES = {258-267},
YEAR = {1989, April},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bar-Noy-Borodin-Karchmer-Linial-Werman/89,
AUTHOR = {Bar-Noy, Amotz and Borodin, Allan and Karchmer, Mauricio and Linial, Nathan and Werman, Michael},
TITLE = {Bounds on universal sequences},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
NUMBER = {2},
PAGES = {268-277},
YEAR = {1989, April},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Steele-Snyder/89,
AUTHOR = {Steele, J. Michael and Snyder, Timothy Law},
TITLE = {Worst-case growth rates of some classical problems of combinatorial optimization},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
NUMBER = {2},
PAGES = {278-287},
YEAR = {1989, April},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Hagerup-Chrobak-Diks/89,
AUTHOR = {Hagerup, Torben and Chrobak, Marek and Diks, Krzysztof},
TITLE = {Optimal parallel 5-colouring of planar graphs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
NUMBER = {2},
PAGES = {288-300},
YEAR = {1989, April},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Melen-Turner/89,
AUTHOR = {Melen, Riccardo and Turner, Jonathan S.},
TITLE = {Nonblocking multirate networks},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
NUMBER = {2},
PAGES = {301-313},
YEAR = {1989, April},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Leung-Young/89,
AUTHOR = {Leung, Joseph Y.-T. and Young, Gilbert H.},
TITLE = {Minimizing schedule length subject to minimum flow time},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
NUMBER = {2},
PAGES = {314-326},
YEAR = {1989, April},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Naor-Naor-Schaffer/89,
AUTHOR = {Naor, Joseph and Naor, Moni and Sch{\"a}ffer, Alejandro A.},
TITLE = {Fast parallel algorithms for chordal graphs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
NUMBER = {2},
PAGES = {327-349},
YEAR = {1989, April},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Renegar/89,
AUTHOR = {Renegar, James},
TITLE = {On the worst-case arithmetic complexity of approximating zeros of systems of polynomials},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
NUMBER = {2},
PAGES = {350-370},
YEAR = {1989, April},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Yao-Dobkin-Edelsbrunner-Paterson/89,
AUTHOR = {Yao, F. Frances and Dobkin, David P. and Edelsbrunner, Herbert and Paterson, Michael S.},
TITLE = {Partitioning space for range queries},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
NUMBER = {2},
PAGES = {371-384},
YEAR = {1989, April},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Iwama/89,
AUTHOR = {Iwama, Kazuo},
TITLE = {CNF satisfiability test by counting and polynomial average time},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
NUMBER = {2},
PAGES = {385-391},
YEAR = {1989, April},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Ko/89b,
AUTHOR = {Ko, Ker-I},
TITLE = {Relativized polynomial time hierarchies having exactly $K$ levels},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
NUMBER = {2},
PAGES = {392-408},
YEAR = {1989, April},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bugrara-Pan-Purdom/89,
AUTHOR = {Bugrara, Khaled M. and Pan, Youfang and Purdom, Paul Walton, Jr.},
TITLE = {Exponential average time for the pure literal rule},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
NUMBER = {2},
PAGES = {409-418},
YEAR = {1989, April},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Goldberg-Spencer/89a,
AUTHOR = {Goldberg, Mark and Spencer, Thomas},
TITLE = {A new parallel algorithm for the maximal independent set problem},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
NUMBER = {2},
PAGES = {419-427},
YEAR = {1989, April},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chan/89,
AUTHOR = {Chan, Edward P.F.},
TITLE = {A design theory for solving the anomalies problem},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {429-448},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Tang-Watanabe/89,
AUTHOR = {Tang, Shouwen and Watanabe, Osamu},
TITLE = {On tally relativizations of $BP$-complexity classes},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {449-462},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Li/89,
AUTHOR = {Li, Shuo-Yen Robert},
TITLE = {Dynamic programming by exchangeability},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {463-472},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Rhee-Talagrand/89a,
AUTHOR = {Rhee, Wansoo T. and Talagrand, Michel},
TITLE = {Optimal bin packing with items of random sizes III},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {473-486},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Rhee-Talagrand/89b,
AUTHOR = {Rhee, Wansoo T. and Talagrand, Michel},
TITLE = {Optimal bin covering with items of random size},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {487-498},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Atallah-Cole-Goodrich/89,
AUTHOR = {Atallah, Mikhail J. and Cole, Richard and Goodrich, Michael T.},
TITLE = {Cascading divide-and-conquer: A technique for designing parallel algorithms},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {499-532},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Venkateswaran-Tompa/89,
AUTHOR = {Venkateswaran, H. and Tompa, Martin},
TITLE = {A new peeble game that characterizes parallel complexity classes},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {533-549},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Furst-Kannan/89,
AUTHOR = {Furst, Merrick L. and Kannan, Ravi},
TITLE = {Succinct certificates for almost all subset sum problems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {550-558},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Borodin-Cook-Dymond-Ruzzo-Tompa/89,
AUTHOR = {Borodin, Allan and Cook, Stephen A. and Dymond, Patrick W. and Ruzzo, Walter L. and Tompa, Martin},
TITLE = {Two applications of inductive counting for complementation problems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {559-578},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
NOTE = {see Erratum in SIAM J. Comput., Vol. 18, 1283},
}
@article{Barahona-Tardos/89,
AUTHOR = {Barahona, Francisco and Tardos, Eva},
TITLE = {Note on Weintraub's minimum-cost circulation algorithm},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {579-583},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Clausen/89,
AUTHOR = {Clausen, Michael},
TITLE = {Fast Fourier transforms for metabelian groups},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {584-593},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Rajasekaran-Reif/89,
AUTHOR = {Rajasekaran, Sanguthevar and Reif, John H.},
TITLE = {Optimal and sublogarithmic time randomized parallel sorting algorithms},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {594-607},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Norton/89,
AUTHOR = {Norton, G.H.},
TITLE = {Precise analyses of the right- and left-shift greatest common divisor algorithms for $GF(q)[x]$},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {608-624},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Immerman/89a,
AUTHOR = {Immerman, Neil},
TITLE = {Expressibility and parallel complexity},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {625-638},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Labahn-Cabay/89a,
AUTHOR = {Labahn, George and Cabay, Stan},
TITLE = {Matrix Pad{\'e} fractions and their computation},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {639-657},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Iliopoulos/89a,
AUTHOR = {Iliopoulos, Costas S.},
TITLE = {Worst-case complexity bounds on algorithms for computing the canonical structure of finite Abelian groups and the Hermite and Smith normal forms of an integer matrix},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {658-669},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Iliopoulos/89,
AUTHOR = {Iliopoulos, Costas S.},
TITLE = {Worst-case complexity bounds on algorithms for computing the canonical structure of infinite Abelian groups and solving systems of linear Diophantine equations},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {670-678},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Yao/89b,
AUTHOR = {Yao, Andrew Chi-Chih},
TITLE = {On the complexity of partial order productions},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {679-689},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Simons-Warmuth/89,
AUTHOR = {Simons, Barbara B. and Warmuth, Manfred K.},
TITLE = {A fast algorithm for multiprocessor scheduling of unit-length jobs},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {690-710},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Galil-Haber-Yungs/89,
AUTHOR = {Galil, Zvi and Haber, Stuart and Yungs, Moti},
TITLE = {Minimum-knowledge interactive proofs for decision problems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {711-739},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Peleg-Ullman/89,
AUTHOR = {Peleg, David and Ullman, Jeffrey D.},
TITLE = {An optimal synchronizer for the hypercube},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {740-747},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Vaidya/89c,
AUTHOR = {Vaidya, Pravin M.},
TITLE = {Space-time trade-offs for orthogonal range queries},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {748-758},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bshouty/89a,
AUTHOR = {Bshouty, Nader H.},
TITLE = {A lower bound for matrix multiplication},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {759-765},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bennett/89,
AUTHOR = {Bennett, Charles H.},
TITLE = {Time/space trade-offs for reversible computation},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {766-776},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Jacquet-Szpankowski/89,
AUTHOR = {Jacquet, Philippe and Szpankowski, Wojciech},
TITLE = {Ultimate characterizations of the burst response of an interval searching algorithm: A study of a functional equation},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {777-791},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Cole-Salowe-Steiger-Szemeredi/89,
AUTHOR = {Cole, Richard and Salowe, Jeffrey S. and Steiger, W.L. and Szemer{\'e}di, Endre},
TITLE = {An optimal-time algorithm for slope selection},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {792-810},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Preparata-Tamassia/89,
AUTHOR = {Preparata, Franco P. and Tamassia, Roberto},
TITLE = {Fully dynamic point location in a monotone subdivision},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {811-830},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Culik-Pachl-Yu/89,
AUTHOR = {Culik II, Karel and Pachl, Jan and Yu, Sheng},
TITLE = {On the limit sets of cellular automata},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {831-842},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Frederickson-Janardan/89,
AUTHOR = {Frederickson, Greg N. and Janardan, Ravi},
TITLE = {Efficient message routing in planar networks},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {843-857},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Hastad-Just-Lagarias-Schnorr/89,
AUTHOR = {H{\aa}stad, J. and Just, B. and Lagarias, J.C. and Schnorr, C.P.},
TITLE = {Polynomial time algorithms for finding integer relations among real numbers},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
NUMBER = {5},
PAGES = {859-881},
YEAR = {1989, October},
NOTE = {see Erratum in SIAM J. Comput., Vol. 43, 2014, No. 1, 254-254},
}
@article{Anily-Hassin/89,
AUTHOR = {Anily, S. and Hassin, R.},
TITLE = {Ranking the best binary trees},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {882-892},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Cherry/89,
AUTHOR = {Cherry, G.W.},
TITLE = {An analysis of the rational exponential integral},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {893-905},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Verma-Reyner/89,
AUTHOR = {Verma, Rakesh M. and Reyner, Steven W.},
TITLE = {An analysis of a good algorithm for the subtree problem, corrected},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {906-908},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Rhee-Talagrand/89,
AUTHOR = {Rhee, Wansoo T. and Talagrand, Michel},
TITLE = {The complete convergence of best fit decreasing},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {909-918},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Rhee-Talagrand/89d,
AUTHOR = {Rhee, Wansoo T. and Talagrand, Michel},
TITLE = {The complete convergence of first fit decreasing},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {919-938},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Ahuja-Orlin-Tarjan/89,
AUTHOR = {Ahuja, Ravindra K. and Orlin, James B. and Tarjan, Robert E.},
TITLE = {Improved time bounds for the maximum flow problem},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {939-954},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Eberly/89,
AUTHOR = {Eberly, Wayne},
TITLE = {Very fast parallel polynomial arithmetic},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {955-976},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Doberkat/89,
AUTHOR = {Doberkat, Ernst-Erich},
TITLE = {Topological completeness in an ideal model for polymorphic types},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {977-989},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Coan-Dolev-Dwork-Stockmeyer/89,
AUTHOR = {Coan, Brian A. and Dolev, Danny and Dwork, Cynthia and Stockmeyer, Larry},
TITLE = {The distributed firing squad problem},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {990-1012},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Gabow-Tarjan/89,
AUTHOR = {Gabow, Harold N. and Tarjan, Robert E.},
TITLE = {Faster scaling algorithms for network problems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {1013-1036},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Brown-Finkelstein-Purdom/89,
AUTHOR = {Brown, Cynthia A. and Finkelstein, Larry and Purdom, Paul W., Jr.},
TITLE = {A new base change algorithm for permutation groups},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {1037-1047},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Humenik/89,
AUTHOR = {Humenik, Keith},
TITLE = {Ratio estimators are maximum-likelihood estimators for non-context-free grammars},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {1048-1055},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Cheriyan-Maheshwari/89,
AUTHOR = {Cheriyan, J. and Maheshwari, S.N.},
TITLE = {Analysis of preflow push algorithms for maximum network flow},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {1057-1086},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Ladner/89,
AUTHOR = {Ladner, Richard E.},
TITLE = {Polynomial space counting problems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {1087-1097},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Bernstein-Jaffe-Rodeh/89,
AUTHOR = {Bernstein, David and Jaffe, Jeffrey M. and Rodeh, Michael},
TITLE = {Scheduling arithmetic and load operations in parallel with no spilling},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {1098-1127},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Rappaport/89,
AUTHOR = {Rappaport, David},
TITLE = {Computing simple circuits from a set of line segments is $NP$-complete},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {1128-1139},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Vazirani-Vazirani/89,
AUTHOR = {Vazirani, Umesh V. and Vazirani, Vijay V.},
TITLE = {The two-processor scheduling problem is in random $NC$},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {1140-1148},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Jerrum-Sinclair/89,
AUTHOR = {Jerrum, Mark and Sinclair, Alistair},
TITLE = {Approximating the permanent},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {1149-1178},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Schimmler-Starke/89,
AUTHOR = {Schimmler, Manfred and Starke, Christoph},
TITLE = {A correction network for $N$-sorters},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {1179-1187},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Li-Reingold/89,
AUTHOR = {Li, Zhiyuan and Reingold, Edward M.},
TITLE = {Solution of a divide-and-conquer maximin recurrence},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {1188-1200},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Vaidya/89d,
AUTHOR = {Vaidya, Pravin M.},
TITLE = {Geometry helps in matching},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {1201-1225},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Chen-Shin/89,
AUTHOR = {Chen, Ming-Syan and Shin, Kang G.},
TITLE = {On relaxed squashed embedding of graphs into a hypercube},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {1226-1244},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Zhang-Shasha/89,
AUTHOR = {Zhang, Kaizhong and Shasha, Dennis},
TITLE = {Simple fast algorithms for the editing distance between trees and related problems},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {1245-1262},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}
@article{Ravikumar-Ibarra/89,
AUTHOR = {Ravikumar, Bala and Ibarra, Oscar H.},
TITLE = {Relating the type of ambiguity of finite automata to the succinctness of their representation},
JOURNAL = {SIAM J. Comput.},
VOLUME = {18},
PAGES = {1263-1282},
YEAR = {1989},
PUBLISHER = {Society for Industrial and Applied Mathematics},
ADDRESS = {Philadelphia, PA},
}