Jouannaud, Jean-Pierre; Kirchner, Hélène Completion of a set of rules modulo a set of equations. (English) Zbl 0665.03005 SIAM J. Comput. 15, 1155-1194 (1986). Reviewer: A.Pettorossi MSC: 03B25 08B05 68Q65 03C05 × Cite Format Result Cite Review PDF Full Text: DOI
Orponen, Pekka; Russo, David A.; Schöning, Uwe Optimal approximations and polynomially levelable sets. (English) Zbl 0644.68054 SIAM J. Comput. 15, 399-408 (1986). Reviewer: G.Mauri MSC: 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Prill, David On approximations and incidence in cylindrical algebraic decompositions. (English) Zbl 0643.14002 SIAM J. Comput. 15, 972-993 (1986). Reviewer: A.Holme MSC: 14-04 14Pxx 68W30 × Cite Format Result Cite Review PDF Full Text: DOI
Turner, Jonathan S. On the probable performance of heuristics for bandwidth minimization. (English) Zbl 0637.68050 SIAM J. Comput. 15, 561-580 (1986). Reviewer: A.K.Dewdney MSC: 68Q25 68R10 05C50 05C35 × Cite Format Result Cite Review PDF Full Text: DOI Link
Cabay, Stanley; Choi, Dongkoo Algebraic computations of scaled Padé fractions. (English) Zbl 0633.30008 SIAM J. Comput. 15, 243-270 (1986). Reviewer: M.Eiermann MSC: 30B70 41A21 65E05 68W30 65D05 × Cite Format Result Cite Review PDF Full Text: DOI
Davenport, J. H. The Risch differential equation problem. (English) Zbl 0632.65091 SIAM J. Comput. 15, 903-918 (1986). MSC: 65L05 68W30 12H20 × Cite Format Result Cite Review PDF Full Text: DOI
Shub, M.; Smale, S. Computational complexity: On the geometry of polynomials and a theory of cost. II. (English) Zbl 0625.65036 SIAM J. Comput. 15, 145-161 (1986). Reviewer: J.Oliver MSC: 65H05 68Q25 30C15 × Cite Format Result Cite Review PDF Full Text: DOI Link
Blum, Lenore; Shub, Michael Evaluating rational functions: Infinite precision is finite cost and tractable on average. (English) Zbl 0622.68038 SIAM J. Comput. 15, 384-398 (1986). Reviewer: M.Chytil MSC: 68Q25 65G99 26C15 28A75 × Cite Format Result Cite Review PDF Full Text: DOI Link
Johnson, Rodney W.; McLoughlin, Aileen M. Noncommutative bilinear algorithms for 3\(\times 3\) matrix multiplication. (English) Zbl 0622.68037 SIAM J. Comput. 15, 595-603 (1986). Reviewer: M.Chytil MSC: 68Q25 65F30 15A99 68W30 68W99 × Cite Format Result Cite Review PDF Full Text: DOI
Balćzar, José L.; Book, Ronald V.; Schöning, Uwe Sparse sets, lowness and highness. (English) Zbl 0621.68033 SIAM J. Comput. 15, 739-747 (1986). MSC: 68Q25 68Q05 03D15 × Cite Format Result Cite Review PDF Full Text: DOI Link
Chao, Ming-Te; Franco, John Probabilistic analysis of two heuristics for the 3-satisfiability problem. (English) Zbl 0621.68031 SIAM J. Comput. 15, 1106-1118 (1986). MSC: 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI Link
Kawaguchi, Tsuyoshi; Kyan, Seiki Worst case bound of an LRF schedule for the mean weighted flow-time problem. (English) Zbl 0621.68024 SIAM J. Comput. 15, 1119-1129 (1986). MSC: 68M20 68Q25 90B35 × Cite Format Result Cite Review PDF Full Text: DOI
Gaver, Donald P.; Jacobs, Patricia A. Processor-shared time-sharing models in heavy traffic. (English) Zbl 0621.68023 SIAM J. Comput. 15, 1085-1100 (1986). MSC: 68M20 68N99 × Cite Format Result Cite Review PDF Full Text: DOI
Luby, Michael A simple parallel algorithm for the maximal independent set problem. (English) Zbl 0619.68058 SIAM J. Comput. 15, 1036-1053 (1986). MSC: 68R10 × Cite Format Result Cite Review PDF Full Text: DOI
Faigle, U.; Lovász, László; Schrader, R.; Turán, Gy. Searching in trees, series-parallel and interval orders. (English) Zbl 0619.68057 SIAM J. Comput. 15, 1075-1084 (1986). MSC: 68P10 68Q25 06A06 × Cite Format Result Cite Review PDF Full Text: DOI
Beame, Paul W.; Cook, Stephen A.; Hoover, H. James Log depth circuits for division and related problems. (English) Zbl 0619.68047 SIAM J. Comput. 15, 994-1003 (1986). MSC: 68Q25 68Q05 94C10 × Cite Format Result Cite Review PDF Full Text: DOI
Huynh, Dung T. Some observations about the randomness of hard problems. (English) Zbl 0619.68046 SIAM J. Comput. 15, 1101-1105 (1986). MSC: 68Q25 68S05 × Cite Format Result Cite Review PDF Full Text: DOI
Pang, King F.; El Gamal, Abbas Communication complexity of computing the Hamming distance. (English) Zbl 0619.68045 SIAM J. Comput. 15, 932-947 (1986). MSC: 68Q25 68N25 × Cite Format Result Cite Review PDF Full Text: DOI
Katz, Martin David; Volper, Dennis J. Data structures for retrieval on square grids. (English) Zbl 0619.68044 SIAM J. Comput. 15, 919-931 (1986). MSC: 68Q25 68P05 68P20 × Cite Format Result Cite Review PDF Full Text: DOI
Hirschberg, D. S.; Larmore, L. L. Average case analysis of marking algorithms. (English) Zbl 0619.68043 SIAM J. Comput. 15, 1069-1074 (1986). MSC: 68Q25 68P05 × Cite Format Result Cite Review PDF Full Text: DOI Link
Gonnet, Gaston H.; Munro, J. Ian Heaps on heaps. (English) Zbl 0619.68042 SIAM J. Comput. 15, 964-971 (1986). MSC: 68Q25 68P05 68P10 × Cite Format Result Cite Review PDF Full Text: DOI
Li, Liwu Ranking and unranking of AVL-trees. (English) Zbl 0619.68041 SIAM J. Comput. 15, 1025-1035 (1986). MSC: 68Q25 68R10 05C05 × Cite Format Result Cite Review PDF Full Text: DOI
Cunningham, William H. Improved bounds for matroid partition and intersection algorithms. (English) Zbl 0619.68040 SIAM J. Comput. 15, 948-957 (1986). MSC: 68Q25 05B35 × Cite Format Result Cite Review PDF Full Text: DOI
Blum, Norbert On the single-operation worst-case time complexity of the disjoint set union problem. (English) Zbl 0619.68039 SIAM J. Comput. 15, 1021-1024 (1986). MSC: 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Ja’ja’, Joseph; Takche, Jean On the validity of the direct sum conjecture. (English) Zbl 0619.68037 SIAM J. Comput. 15, 1004-1020 (1986). MSC: 68W30 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Sleator, Daniel Dominic; Tarjan, Robert Endre Self-adjusting heaps. (English) Zbl 0618.68017 SIAM J. Comput. 15, 52-69 (1986). MSC: 68P05 68R99 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI Link
Ambos-Spies, Klaus An inhomogeneity in the structure of Karp degrees. (English) Zbl 0618.03018 SIAM J. Comput. 15, 958-963 (1986). Reviewer: M.Tetruašvili MSC: 03D15 03D30 × Cite Format Result Cite Review PDF Full Text: DOI
Valiant, L. G. Negation is powerless for Boolean slice functions. (English) Zbl 0616.94020 SIAM J. Comput. 15, 531-535 (1986). Reviewer: A.Michalski MSC: 94C10 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Wright, Robert Alan; Richmond, Bruce; Odlyzko, Andrew; McKay, Brendan D. Constant time generation of free trees. (English) Zbl 0616.68063 SIAM J. Comput. 15, 540-548 (1986). Reviewer: J.Ebert MSC: 68R10 05C05 × Cite Format Result Cite Review PDF Full Text: DOI
Friedman, Joel Constructing O(n log n) size monotone formulae for the kth threshold function of n Boolean variables. (English) Zbl 0613.94011 SIAM J. Comput. 15, 641-654 (1986). MSC: 94C10 94B05 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Dyer, M. E. On a multidimensional search technique and its application to the Euclidean one-centre problem. (English) Zbl 0613.68044 SIAM J. Comput. 15, 725-738 (1986). MSC: 68U99 90C05 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Edelsbrunner, H.; Welzl, E. Constructing belts in two-dimensional arrangements with applications. (English) Zbl 0613.68043 SIAM J. Comput. 15, 271-284 (1986). MSC: 68U99 51A20 52A10 × Cite Format Result Cite Review PDF Full Text: DOI
Willard, Dan E. Log-logarithmic selection resolution protocols in a multiple access channel. (English) Zbl 0612.94001 SIAM J. Comput. 15, 468-477 (1986). MSC: 94A05 68Q25 94A40 68M20 × Cite Format Result Cite Review PDF Full Text: DOI
Sharir, Micha; Schorr, Amir On shortest paths in polyhedral spaces. (English) Zbl 0612.68090 SIAM J. Comput. 15, 193-215 (1986). MSC: 68U99 68Q25 52Bxx × Cite Format Result Cite Review PDF Full Text: DOI Backlinks: MO
Chazelle, Bernard Filtering search: a new approach to query-answering. (English) Zbl 0612.68088 SIAM J. Comput. 15, 703-724 (1986). MSC: 68P20 68P10 × Cite Format Result Cite Review PDF Full Text: DOI
Hull, Richard Relative information capacity of simple relational database schemata. (English) Zbl 0612.68085 SIAM J. Comput. 15, 856-886 (1986). MSC: 68P20 × Cite Format Result Cite Review PDF Full Text: DOI
Flajolet, P.; Prodinger, H. Register allocation for unary-binary trees. (English) Zbl 0612.68065 SIAM J. Comput. 15, 629-640 (1986). MSC: 68R99 68N99 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Leighton, Frank Thomson; Rosenberg, Arnold L. Three-dimensional circuit layouts. (English) Zbl 0612.68063 SIAM J. Comput. 15, 793-813 (1986). MSC: 68R10 68Q25 94C15 05C99 × Cite Format Result Cite Review PDF Full Text: DOI
Baker, Brenda S. A provably good algorithm for the two module routing problem. (English) Zbl 0612.68062 SIAM J. Comput. 15, 162-188 (1986). MSC: 68R10 68Q25 94C15 × Cite Format Result Cite Review PDF Full Text: DOI
Smith, Justin R. Parallel algorithms for depth-first searches. I. Planar graphs. (English) Zbl 0612.68059 SIAM J. Comput. 15, 814-830 (1986). MSC: 68P10 68Q25 68R10 × Cite Format Result Cite Review PDF Full Text: DOI
Cherry, G. W. Integration in finite terms with special functions: the logarithmic integral. (English) Zbl 0612.12019 SIAM J. Comput. 15, 1-21 (1986). Reviewer: G. W. Cherry MSC: 12H05 65D20 68W30 × Cite Format Result Cite Review PDF Full Text: DOI
O’Rourke, Joseph The signature of a plane curve. (English) Zbl 0611.68061 SIAM J. Comput. 15, 34-51 (1986). MSC: 68U99 52A10 68T10 51M05 68P10 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Citrini, Claudio; Crespi-Reghizzi, Stefano; Mandrioli, Dino On deterministic multi-pass analysis. (English) Zbl 0611.68051 SIAM J. Comput. 15, 668-693 (1986). MSC: 68Q45 68N20 68Q05 × Cite Format Result Cite Review PDF Full Text: DOI
Flajolet, Philippe; Sedgewick, Robert Digital search trees revisited. (English) Zbl 0611.68041 SIAM J. Comput. 15, 748-767 (1986). MSC: 68P10 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI Link
Irving, Robert W.; Leather, Paul The complexity of counting stable marriages. (English) Zbl 0611.68015 SIAM J. Comput. 15, 655-667 (1986). MSC: 68Q25 05A05 × Cite Format Result Cite Review PDF Full Text: DOI
Reif, John H. Logaritmic depth circuits for algebraic functions. (English) Zbl 0611.68014 SIAM J. Comput. 15, 231-242 (1986). MSC: 68Q25 68W30 × Cite Format Result Cite Review PDF Full Text: DOI
Geske, John; Grollmann, Joachim Relativizations of unambiguous and random polynomial time classes. (English) Zbl 0609.68038 SIAM J. Comput. 15, 511-519 (1986). MSC: 68Q25 68Q05 03D15 03D10 94A60 × Cite Format Result Cite Review PDF Full Text: DOI
Chazelle, B.; Drysdale, R. L.; Lee, D. T. Computing the largest empty rectangle. (English) Zbl 0608.68059 SIAM J. Comput. 15, 300-315 (1986). MSC: 68R99 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Arazi, Benjamin A binary search with a parallel recovery of the bits. (English) Zbl 0608.68056 SIAM J. Comput. 15, 851-855 (1986). MSC: 68P10 11T99 11S20 12J15 × Cite Format Result Cite Review PDF Full Text: DOI
Kingston, Jeffrey H. Analysis of Henriksen’s algorithm for the simulation event set. (English) Zbl 0606.68102 SIAM J. Comput. 15, 887-902 (1986). MSC: 68U20 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Provan, J. Scott The complexity of reliability computations in planar and acyclic graphs. (English) Zbl 0606.68066 SIAM J. Comput. 15, 694-702 (1986). MSC: 68R10 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI DOI Link
Bach, Eric; Miller, Gary; Shallit, Jeffrey Sums of divisors, perfect numbers and factoring. (English) Zbl 0606.10003 SIAM J. Comput. 15, 1143-1154 (1986). Reviewer: Jeffrey Shallitt MSC: 11Y16 11Y05 11Y70 11A25 68W20 × Cite Format Result Cite Review PDF Full Text: DOI Link
Balas, Egon; Yu, Changsung Finding a maximum clique in an arbitrary graph. (English) Zbl 0604.05024 SIAM J. Comput. 15, 1054-1068 (1986). MSC: 05C35 68R10 05-04 × Cite Format Result Cite Review PDF Full Text: DOI
Edelsbrunner, H.; O’Rourke, J.; Seidel, R. Constructing arrangements of lines and hyperplanes with applications. (English) Zbl 0603.68104 SIAM J. Comput. 15, 341-363 (1986). MSC: 68U05 68Q25 51M20 52Bxx 52A37 × Cite Format Result Cite Review PDF Full Text: DOI
Maass, Wolfgang On the complexity of nonconvex covering. (English) Zbl 0603.68103 SIAM J. Comput. 15, 453-467 (1986). MSC: 68U99 68Q25 51M20 × Cite Format Result Cite Review PDF Full Text: DOI
Huynh, Dung T. The complexity of the membership problem for two subclasses of polynomial ideals. (English) Zbl 0603.68038 SIAM J. Comput. 15, 581-594 (1986). MSC: 68W30 68Q25 13F20 13A15 × Cite Format Result Cite Review PDF Full Text: DOI
Manber, Udi On maintaining dynamic information in a concurrent environment. (English) Zbl 0603.68023 SIAM J. Comput. 15, 1130-1142 (1986). MSC: 68N25 68W99 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI Link
Edelsbrunner, Herbert; Guibas, Leonidas J.; Stolfi, Jorge Optimal point location in a monotone subdivision. (English) Zbl 0602.68102 SIAM J. Comput. 15, 317-340 (1986). MSC: 68U99 68R10 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI Link
Ausiello, G.; D’Atri, A.; Saccà, D. Minimal representation of directed hypergraphs. (English) Zbl 0602.68056 SIAM J. Comput. 15, 418-431 (1986). MSC: 68R10 05C65 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Feigenbaum, Joan; Schäffer, Alejandro A. Recognizing composite graphs is equivalent to testing graph isomorphism. (English) Zbl 0602.68033 SIAM J. Comput. 15, 619-627 (1986). MSC: 68Q25 05C99 × Cite Format Result Cite Review PDF Full Text: DOI
Blum, L.; Blum, M.; Shub, M. A simple unpredictable pseudo-random number generator. (English) Zbl 0602.65002 SIAM J. Comput. 15, 364-383 (1986). Reviewer: J.Král MSC: 65C10 94A60 × Cite Format Result Cite Review PDF Full Text: DOI Link
von zur Gathen, Joachim Representations and parallel computations for rational functions. (English) Zbl 0599.68036 SIAM J. Comput. 15, 432-452 (1986). Reviewer: W.Schönauer MSC: 68W30 68Q25 41A20 × Cite Format Result Cite Review PDF Full Text: DOI
Otto, Friedrich Church-Rosser Thue systems that present free monoids. (English) Zbl 0599.20091 SIAM J. Comput. 15, 786-792 (1986). Reviewer: K.Peeva MSC: 20M05 03D03 × Cite Format Result Cite Review PDF Full Text: DOI
Hunt, H. B. III; Rosenkrantz, D. J. Recursion schemes and recursive programs are exponentially hard to analyze. (English) Zbl 0598.68017 SIAM J. Comput. 15, 831-850 (1986). MSC: 68Q60 68N01 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Hopcroft, J. E.; Wilfong, G. T. Reducing multiple object motion planning to graph searching. (English) Zbl 0596.05043 SIAM J. Comput. 15, 768-785 (1986). MSC: 05C40 68Q25 68R10 × Cite Format Result Cite Review PDF Full Text: DOI Link
Bruno, John L.; Downey, Peter J. Probabilistic bounds on the performance of list scheduling. (English) Zbl 0595.68037 SIAM J. Comput. 15, 409-417 (1986). Reviewer: A.Kolen MSC: 68M20 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Frieze, A. M. On the Lagarias-Odlyzko algorithm for the subset sum problem. (English) Zbl 0592.94010 SIAM J. Comput. 15, 536-539 (1986). MSC: 94A99 11T99 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Matsumoto, Kazuhiko; Nishizeki, Takao; Saito, Nobuji Planar multicommodity flows, maximum matchings and negative cycles. (English) Zbl 0592.05024 SIAM J. Comput. 15, 495-510 (1986). MSC: 05C20 05C70 90B10 05C38 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Imai, Hiroshi; Asano, Takao Efficient algorithms for geometric graph search problems. (English) Zbl 0591.68068 SIAM J. Comput. 15, 478-494 (1986). MSC: 68R10 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI Link
Berman, Francine; Bock, Mary Ellen; Dittert, Eric; O’Donnell, Michael J.; Plank, Darrell Collections of functions for perfect hashing. (English) Zbl 0591.68059 SIAM J. Comput. 15, 604-618 (1986). MSC: 68P10 × Cite Format Result Cite Review PDF Full Text: DOI
Cook, Stephen; Dwork, Cynthia; Reischuk, Rüdiger Upper and lower time bounds for parallel random access machines without simultaneous writes. (English) Zbl 0591.68049 SIAM J. Comput. 15, 87-97 (1986). MSC: 68Q05 68Q25 68P10 × Cite Format Result Cite Review PDF Full Text: DOI
Chin, Francis; Ramarao, K. V. S. Optimal termination protocols for network partitioning. (English) Zbl 0589.68069 SIAM J. Comput. 15, 131-144 (1986). MSC: 68P20 × Cite Format Result Cite Review PDF Full Text: DOI Link
Engelfriet, Joost The complexity of languages generated by attribute grammars. (English) Zbl 0589.68055 SIAM J. Comput. 15, 70-86 (1986). MSC: 68Q45 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Etzion, T.; Lempel, A. An efficient algorithm for generating linear transformations in a shuffle-exchange network. (English) Zbl 0589.68052 SIAM J. Comput. 15, 216-221 (1986). MSC: 68R10 68N25 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI Link
Galil, Zvi; Micali, Silvio; Gabow, Harold On O(EV log V) algorithm for finding a maximal weighted matching in general graphs. (English) Zbl 0589.68050 SIAM J. Comput. 15, 120-130 (1986). MSC: 68R10 05C70 90B10 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Langenhop, Carl E.; Wright, William E. Probabilities related to father-son distances in binary search trees. (English) Zbl 0589.68049 SIAM J. Comput. 15, 520-530 (1986). MSC: 68P10 × Cite Format Result Cite Review PDF Full Text: DOI
Mehlhorn, Kurt; Tsakalidis, Athanasios An amortized analysis of insertions into AVL-trees. (English) Zbl 0589.68048 SIAM J. Comput. 15, 22-33 (1986). MSC: 68P10 × Cite Format Result Cite Review PDF Full Text: DOI
Apostolico, Alberto; Giancarlo, Raffaele The Boyer-Moore-Galil string searching strategies revisited. (English) Zbl 0589.68047 SIAM J. Comput. 15, 98-119 (1986). MSC: 68P10 × Cite Format Result Cite Review PDF Full Text: DOI Link
Friesen, D. K.; Langston, M. A. Variable sized bin packing. (English) Zbl 0589.68036 SIAM J. Comput. 15, 222-230 (1986). MSC: 68R99 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Kirkpatrick, David G.; Seidel, Raimund The ultimate planar convex hull algorithm ? (English) Zbl 0589.68035 SIAM J. Comput. 15, 287-299 (1986). MSC: 68Q25 52-04 52A10 × Cite Format Result Cite Review PDF Full Text: DOI Link
Borodin, Allan; Dolev, Danny; Fich, Faith E.; Paul, Wolfgang Bounds for width two branching programs. (English) Zbl 0589.68034 SIAM J. Comput. 15, 549-560 (1986). MSC: 68Q25 94C10 68R10 × Cite Format Result Cite Review PDF Full Text: DOI
Levin, Leonid A. Average case complete problems. (English) Zbl 0589.68032 SIAM J. Comput. 15, 285-286 (1986). MSC: 68Q25 × Cite Format Result Cite Review PDF Full Text: DOI
Coppersmith, D.; Klawe, M. M.; Pippenger, N. J. Alphabetic minimax trees of degree at most t. (English) Zbl 0587.94019 SIAM J. Comput. 15, 189-192 (1986). MSC: 94C10 94C15 × Cite Format Result Cite Review PDF Full Text: DOI Link
Meyer auf der Heide, Friedhelm Efficient simulations among several models of parallel computers. (English) Zbl 0545.68043 SIAM J. Comput. 15, 106-119 (1986). MSC: 68Q05 68Q25 68N25 68Q65 × Cite Format Result Cite Review PDF Full Text: DOI Link