Lickteig, Thomas The computational complexity of division in quadratic extension fields. (English) Zbl 0686.68040 SIAM J. Comput. 16, 278-311 (1987). Reviewer: H.Alt MSC: 68W30 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Hunt, H. B. III; Stearns, R. E. Nonlinear algebra and optimization on rings are “hard”. (English) Zbl 0686.68037 SIAM J. Comput. 16, 910-929 (1987). Reviewer: H.Alt MSC: 68Q25 68W30 13A99 16Y99 × Cite Format Result Cite Review PDF Full Text: DOI
Gasarch, William Oracles for deterministic versus alternating classes. (English) Zbl 0686.68036 SIAM J. Comput. 16, 613-627 (1987). Reviewer: H.Alt MSC: 68Q25 03D15 × Cite Format Result Cite Review PDF Full Text: DOI
Kannan, Ravindran; Miller, Gary; Rudolph, Larry Sublinear parallel algorithm for computing the greatest common divisor of two integers. (English) Zbl 0656.10002 SIAM J. Comput. 16, 7-16 (1987). Reviewer: J.Liang MSC: 11-04 11A05 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI Link
Frieze, A. M. On the exact solution of random travelling salesman problems with medium size integer coefficients. (English) Zbl 0654.90095 SIAM J. Comput. 16, 1052-1072 (1987). MSC: 90C35 68Q25 90C27 90C10 68S05 × Cite Format Result Cite Review PDF Full Text: DOI
Chan, Edward P. F.; Mendelzon, Alberto O. Independent and separable database schemes. (English) Zbl 0654.68112 SIAM J. Comput. 16, 841-851 (1987). Reviewer: J.Sefránek MSC: 68P20 68Q99 68P05 × Cite Format Result Cite Review PDF Full Text: DOI
Tamassia, Roberto On embedding a graph in the grid with the minimum number of bends. (English) Zbl 0654.68090 SIAM J. Comput. 16, 421-444 (1987). MSC: 68R10 05C10 94C15 90B10 68U99 × Cite Format Result Cite Review PDF Full Text: DOI
Moffat, Alistair; Takaoka, Tadao An all pairs shortest path algorithm with expected time \(O(n^ 2\,\log \,n)\). (English) Zbl 0654.68088 SIAM J. Comput. 16, 1023-1031 (1987). MSC: 68R10 68Q25 05C38 05C80 × Cite Format Result Cite Review PDF Full Text: DOI
Frederickson, Greg N. Fast algorithms for shortest paths in planar graphs, with applications. (English) Zbl 0654.68087 SIAM J. Comput. 16, 1004-1022 (1987). MSC: 68R10 68Q25 05C38 68P05 × Cite Format Result Cite Review PDF Full Text: DOI Link
Gurevich, Yuri; Shelah, Saharon Expected computation time for Hamiltonian path problem. (English) Zbl 0654.68083 SIAM J. Comput. 16, 486-502 (1987). MSC: 68R10 68Q25 05C38 05C80 60C05 × Cite Format Result Cite Review PDF Full Text: DOI Link
Vaishnavi, Vijay K. Weighted leaf AVL-trees. (English) Zbl 0654.68077 SIAM J. Comput. 16, 503-537 (1987). MSC: 68P10 68P05 68P20 × Cite Format Result Cite Review PDF Full Text: DOI
Larmore, Lawrence L. Height restricted optimal binary trees. (English) Zbl 0654.68076 SIAM J. Comput. 16, 1115-1123 (1987). MSC: 68P10 68P20 94B99 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Hu, T. C.; Wachs, Michelle L. Binary search on a tape. (English) Zbl 0654.68075 SIAM J. Comput. 16, 573-590 (1987). MSC: 68P10 68P05 05C05 68Q25 68P20 × Cite Format Result Cite Review PDF Full Text: DOI
Oommen, B. John; Hansen, E. R. List organizing strategies using stochastic move-to-front and stochastic move-to-rear operations. (English) Zbl 0654.68074 SIAM J. Comput. 16, 705-716 (1987). MSC: 68P10 68P20 68P05 × Cite Format Result Cite Review PDF Full Text: DOI
Hofri, Micha; Konheim, Alan G. Padded lists revisited. (English) Zbl 0654.68073 SIAM J. Comput. 16, 1073-1114 (1987). MSC: 68P10 68P05 × Cite Format Result Cite Review PDF Full Text: DOI
Paige, Robert; Tarjan, Robert E. Three partition refinement algorithms. (English) Zbl 0654.68072 SIAM J. Comput. 16, 973-989 (1987). MSC: 68P10 68Q25 68P05 × Cite Format Result Cite Review PDF Full Text: DOI
Yang, Mark C. K.; Huang, Jun S.; Chow, Yuan-Chieh Optimal parallel sorting scheme by order statistics. (English) Zbl 0654.68071 SIAM J. Comput. 16, 990-1003 (1987). MSC: 68P10 62G30 68P05 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Azar, Yossi; Vishkin, Uzi Tight comparison bounds on the complexity of parallel sorting. (English) Zbl 0654.68070 SIAM J. Comput. 16, 458-464 (1987). MSC: 68P10 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI Link
Pippenger, Nicholas Sorting and selecting in rounds. (English) Zbl 0654.68068 SIAM J. Comput. 16, 1032-1038 (1987). MSC: 68P10 × Cite Format Result Cite Review PDF Full Text: DOI Link
Gonzalez, Teofilo F.; Lee, Sing-Ling A 1.6 approximation algorithm for routing multiterminal nets. (English) Zbl 0654.68038 SIAM J. Comput. 16, 669-704 (1987). MSC: 68Q25 68R10 94C15 × Cite Format Result Cite Review PDF Full Text: DOI
Papadimitriou, Christos H.; Yannakakis, Mihalis The complexity of reliable concurrency control. (English) Zbl 0654.68034 SIAM J. Comput. 16, 538-553 (1987). MSC: 68M20 68Q25 68P20 × Cite Format Result Cite Review PDF Full Text: DOI
Friesen, Donald K. Tighter bounds for LPT scheduling on uniform processors. (English) Zbl 0654.68033 SIAM J. Comput. 16, 554-560 (1987). MSC: 68M20 90B35 × Cite Format Result Cite Review PDF Full Text: DOI
Mekler, Alan H.; Nelson, Evelyn M. Equational bases for if-then-else. (English) Zbl 0654.68029 SIAM J. Comput. 16, 465-485 (1987). MSC: 68Q65 08B05 68Q60 × Cite Format Result Cite Review PDF Full Text: DOI
Toueg, Sam; Perry, Kenneth J.; Srikanth, T. K. Fast distributed agreement. (English) Zbl 0654.68016 SIAM J. Comput. 16, 445-457 (1987). MSC: 68N99 × Cite Format Result Cite Review PDF Full Text: DOI
Scheinerman, Edward R. Almost sure fault tolerance in random graphs. (English) Zbl 0654.68015 SIAM J. Comput. 16, 1124-1134 (1987). MSC: 68N99 05C80 68R10 × Cite Format Result Cite Review PDF Full Text: DOI
Hirschberg, D. S.; Larmore, L. L. The least weight subsequence problem. (English) Zbl 0651.68092 SIAM J. Comput. 16, 628-638 (1987). MSC: 68R99 68Q25 68P05 90C39 × Cite Format Result Cite Review PDF Full Text: DOI Link
Papadimitriou, Christos H.; Ullman, Jeffrey D. A communication-time tradeoff. (English) Zbl 0649.68048 SIAM J. Comput. 16, 639-646 (1987). MSC: 68Q25 68R10 68N25 × Cite Format Result Cite Review PDF Full Text: DOI
McKenzie, Pierre; Cook, Stephen A. The parallel complexity of abelian permutation group problems. (English) Zbl 0647.68045 SIAM J. Comput. 16, 880-909 (1987). Reviewer: K.G.Brokate MSC: 68Q25 20K01 68W30 20B35 05C25 × Cite Format Result Cite Review PDF Full Text: DOI
Abrahamson, Karl Generalized string matching. (English) Zbl 0646.68079 SIAM J. Comput. 16, 1039-1051 (1987). MSC: 68P10 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Ibarra, Oscar H.; Jiang, Tao On one-way cellular arrays. (English) Zbl 0646.68070 SIAM J. Comput. 16, 1135-1154 (1987). MSC: 68Q80 68Q25 68Q45 × Cite Format Result Cite Review PDF Full Text: DOI
Hunt, H. B. III; Rosenkrantz, D. J.; Bloniarz, P. A. On the computational complexity of algebra on lattices. (English) Zbl 0642.06005 SIAM J. Comput. 16, 129-148 (1987). Reviewer: J.Neggers (Tuscaloosa) MSC: 06B25 68Q25 06D99 68Q05 03G10 × Cite Format Result Cite Review PDF Full Text: DOI
Rosier, Louis E.; Yen, Hsu-Chun Logspace hierarchies, polynomial time and the complexity of fairness problems concerning \(\omega\)-machines. (English) Zbl 0638.68031 SIAM J. Comput. 16, 779-807 (1987). Reviewer: E.Heinrich MSC: 68Q25 68Q45 68Q05 × Cite Format Result Cite Review PDF Full Text: DOI
Cole, Richard; Sharir, Micha; Yap, Chee K. On k-hulls and related problems. (English) Zbl 0637.68074 SIAM J. Comput. 16, 61-77 (1987). MSC: 68P10 68Q25 52-04 52A20 × Cite Format Result Cite Review PDF Full Text: DOI
Meyer auf der Heide, Friedhelm; Wigderson, Avi The complexity of parallel sorting. (English) Zbl 0636.68076 SIAM J. Comput. 16, 100-107 (1987). MSC: 68P10 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Borodin, A.; Fich, F.; Meyer auf der Heide, F.; Upfal, E.; Wigderson, A. A time-space tradeoff for element distinctness. (English) Zbl 0636.68040 SIAM J. Comput. 16, 97-99 (1987). MSC: 68Q25 68P10 × Cite Format Result Cite Review PDF Full Text: DOI
von zur Gathen, Joachim Computing powers in parallel. (English) Zbl 0636.68034 SIAM J. Comput. 16, 930-945 (1987). Reviewer: W.Schönauer MSC: 68W30 11A63 68Q25 11T06 × Cite Format Result Cite Review PDF Full Text: DOI
Lenstra, Arjen K. Factoring multivariate polynomials over algebraic number fields. (English) Zbl 0636.12005 SIAM J. Comput. 16, 591-598 (1987). Reviewer: Michael Pohst (Düsseldorf) MSC: 11Y16 11Y40 11R09 68W30 × Cite Format Result Cite Review PDF Full Text: DOI Link
Shmueli, Oded; Itai, Alon Complexity of views: Tree and cyclic schemas. (English) Zbl 0635.68122 SIAM J. Comput. 16, 17-37 (1987). MSC: 68P20 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI Link
Fogelman Soulie, Françoise; Weisbuch, Gérard Random iterations of threshold networks and associative memory. (English) Zbl 0635.68101 SIAM J. Comput. 16, 203-220 (1987). MSC: 68T10 94C10 68Q80 × Cite Format Result Cite Review PDF Full Text: DOI
Jones, Douglas W. A note on bottom-up skew heaps. (English) Zbl 0635.68068 SIAM J. Comput. 16, 108-110 (1987). MSC: 68P10 05-04 68M20 × Cite Format Result Cite Review PDF Full Text: DOI
Gusfield, Dan Three fast algorithms for four problems in stable marriage. (English) Zbl 0635.68036 SIAM J. Comput. 16, 111-128 (1987). Reviewer: J.W.Grzymala-Busse MSC: 68Q25 05C70 68R10 × Cite Format Result Cite Review PDF Full Text: DOI Link
Courcoubetis, C. A.; Reiman, M. I.; Simon, B. Stability of a queueing system with concurrent service and locking. (English) Zbl 0635.68029 SIAM J. Comput. 16, 169-178 (1987). MSC: 68M20 68N99 90B22 60K25 × Cite Format Result Cite Review PDF Full Text: DOI
Choi, Hyeong-Ah; Hakimi, S. Louis Scheduling file transfers for trees and odd cycles. (English) Zbl 0635.68023 SIAM J. Comput. 16, 162-168 (1987). MSC: 68M20 68R10 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Alt, Helmut; Hagerup, Torben; Mehlhorn, Kurt; Preparata, Franco P. Deterministic simulation of idealized parallel computers on more realistic ones. (English) Zbl 0635.68015 SIAM J. Comput. 16, 808-835 (1987). Reviewer: K.Mehlhorn MSC: 68N25 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Miller, Russ; Stout, Quentin F. Data movement techniques for the pyramid computer. (English) Zbl 0635.68011 SIAM J. Comput. 16, 38-60 (1987). MSC: 68N25 68U99 68R10 × Cite Format Result Cite Review PDF Full Text: DOI
Wormald, Nicholas C. Generating random unlabelled graphs. (English) Zbl 0634.68067 SIAM J. Comput. 16, 717-727 (1987). Reviewer: J.Štulc MSC: 68R10 05C30 × Cite Format Result Cite Review PDF Full Text: DOI
Kurtz, Stuart A. A note on randomized polynomial time. (English) Zbl 0634.68041 SIAM J. Comput. 16, 852-853 (1987). MSC: 68Q05 03D10 68Q25 03D15 × Cite Format Result Cite Review PDF Full Text: DOI
Immerman, Neil Languages that capture complexity classes. (English) Zbl 0634.68034 SIAM J. Comput. 16, 760-778 (1987). Reviewer: D.Yu.Grigor’ev MSC: 68Q25 03D15 × Cite Format Result Cite Review PDF Full Text: DOI
Asano, Takao An application of duality to edge-deletion problems. (English) Zbl 0634.68033 SIAM J. Comput. 16, 312-331 (1987). MSC: 68Q25 68R10 05C40 05C35 × Cite Format Result Cite Review PDF Full Text: DOI
Helmbold, David; Mayr, Ernst Two processor scheduling is in \({\mathcal N}{\mathcal C}\). (English) Zbl 0634.68023 SIAM J. Comput. 16, 747-759 (1987). Reviewer: P.Brucker MSC: 68M20 68Q25 90B35 × Cite Format Result Cite Review PDF Full Text: DOI
Huang, Wenqi; Yu, Xiangdong A DNF without regular shortest consensus path. (English) Zbl 0632.68085 SIAM J. Comput. 16, 836-840 (1987). Reviewer: M.Armbrust MSC: 68T15 03B35 06E30 × Cite Format Result Cite Review PDF Full Text: DOI
Culik, Karel II; Karhumäki, Juhani The equivalence problem for single-valued two-way transducers (on NPDT0L languages) is decidable. (English) Zbl 0632.68077 SIAM J. Comput. 16, 221-230 (1987). MSC: 68Q45 20M35 × Cite Format Result Cite Review PDF Full Text: DOI
Korach, E.; Moran, S.; Zaks, S. The optimality of distributive constructions of minimum weight and degree restricted spanning trees in a complete network of processors. (English) Zbl 0632.68065 SIAM J. Comput. 16, 231-236 (1987). MSC: 68R10 68Q25 68N99 × Cite Format Result Cite Review PDF Full Text: DOI
Horton, J. D. A polynomial-time algorithm to find the shortest cycle basis of a graph. (English) Zbl 0632.68064 SIAM J. Comput. 16, 358-366 (1987). MSC: 68R10 68Q25 05C38 05C35 × Cite Format Result Cite Review PDF Full Text: DOI
Ibarra, Oscar H.; Palis, Michael A. On efficient simulations of systolic arrays by random-access machines. (English) Zbl 0632.68049 SIAM J. Comput. 16, 367-377 (1987). MSC: 68Q05 68Q80 × Cite Format Result Cite Review PDF Full Text: DOI
Mosses, Peter D.; Plotkin, Gordon D. On proving limiting completeness. (English) Zbl 0632.68012 SIAM J. Comput. 16, 179-194 (1987). MSC: 68Q60 03B40 × Cite Format Result Cite Review PDF Full Text: DOI
Maass, Wolfgang; Schorr, Amir Speed-up of Turing machines with one work tape and a two-way input tape. (English) Zbl 0631.68050 SIAM J. Comput. 16, 195-202 (1987). Reviewer: M.Kratko MSC: 68Q05 68Q25 03D10 03D15 × Cite Format Result Cite Review PDF Full Text: DOI
Guessarian, Irène; Meseguer, José On the axiomatization of “if-then-else”. (English) Zbl 0628.68032 SIAM J. Comput. 16, 332-357 (1987). Reviewer: G.Ciobanu MSC: 68Q65 68Q60 03C05 × Cite Format Result Cite Review PDF Full Text: DOI
Morrison, John A.; Shepp, Larry A.; van Wyk, Christopher J. A queueing analysis of hashing with lazy deletion. (English) Zbl 0626.60101 SIAM J. Comput. 16, 1155-1164 (1987). MSC: 60K30 68Q45 60K25 × Cite Format Result Cite Review PDF Full Text: DOI Link
Cai, Jin-Yi; Meyer, Gabriele E. Graph minimal uncolorability is \(D^ P\)-complete. (English) Zbl 0626.05017 SIAM J. Comput. 16, 259-277 (1987). MSC: 05C15 05C35 68R10 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Mitchell, Joseph S. B.; Mount, David M.; Papadimitriou, Christos H. The discrete geodesic problem. (English) Zbl 0625.68051 SIAM J. Comput. 16, 647-668 (1987). MSC: 68R99 68U99 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Widmayer, P.; Wu, Y. F.; Wong, C. K. On some distance problems in fixed orientations. (English) Zbl 0625.68049 SIAM J. Comput. 16, 728-746 (1987). MSC: 68R99 × Cite Format Result Cite Review PDF Full Text: DOI
Becker, B.; Hotz, G. On the optimal layout of planar graphs with fixed boundary. (English) Zbl 0625.05020 SIAM J. Comput. 16, 946-972 (1987). MSC: 05C10 57M15 65C05 × Cite Format Result Cite Review PDF Full Text: DOI
Gusfield, Dan Optimal mixed graph augmentation. (English) Zbl 0624.05043 SIAM J. Comput. 16, 599-612 (1987). MSC: 05C40 05C20 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Lubiw, Anna Doubly lexical orderings of matrices. (English) Zbl 0622.05045 SIAM J. Comput. 16, 854-879 (1987). MSC: 05C50 × Cite Format Result Cite Review PDF Full Text: DOI
Sharir, Micha On shortest paths amidst convex polyhedra. (English) Zbl 0619.52006 SIAM J. Comput. 16, 561-572 (1987). Reviewer: E.Jucovič MSC: 52Bxx 05C35 05C38 68U99 × Cite Format Result Cite Review PDF Full Text: DOI
Murgolo, Frank D. An efficient approximation scheme for variable-sized bin packing. (English) Zbl 0618.90081 SIAM J. Comput. 16, 149-161 (1987). MSC: 90C27 68Q25 90C05 × Cite Format Result Cite Review PDF Full Text: DOI
Gusfield, Dan; Martel, Charles; Fernandez-Baca, David Fast algorithms for bipartite network flow. (English) Zbl 0617.90082 SIAM J. Comput. 16, 237-251 (1987). Reviewer: A.Girard MSC: 90C35 68Q25 90B10 90C10 90C05 90C27 × Cite Format Result Cite Review PDF Full Text: DOI
Hofri, Micha; Ross, Keith W. On the optimal control of two queues with server setup times and its analysis. (English) Zbl 0617.60091 SIAM J. Comput. 16, 399-420 (1987). Reviewer: D.Repovš MSC: 60K25 60K30 × Cite Format Result Cite Review PDF Full Text: DOI Link
Aurenhammer, F. Power diagrams: Properties, algorithms and applications. (English) Zbl 0616.52007 SIAM J. Comput. 16, 78-96 (1987). Reviewer: E.Heil MSC: 52Bxx 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Papadimitriou, Christos H.; Tsitsiklis, John N. On stochastic scheduling with in-tree precedence constraints. (English) Zbl 0615.90068 SIAM J. Comput. 16, 1-6 (1987). Reviewer: V.Peteanu MSC: 90B35 90B22 × Cite Format Result Cite Review PDF Full Text: DOI
Bini, D.; Capovani, M. Tensor rank and border rank of band Toeplitz matrices. (English) Zbl 0615.15014 SIAM J. Comput. 16, 252-258 (1987). Reviewer: Yueh-er Kuo MSC: 15A72 15B57 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Knessl, C.; Matkowsky, B. J.; Schuss, Z.; Tier, C. Asymptotic expansions for a closed multiple access system. (English) Zbl 0612.90046 SIAM J. Comput. 16, 378-398 (1987). MSC: 90B22 60K25 × Cite Format Result Cite Review PDF Full Text: DOI