Mannila, Heikki; Ukkonen, Esko Unifications, deunifications, and their complexity. (English) Zbl 0746.68020 BIT 30, No. 4, 599-619 (1990). Reviewer: M.Val’ev MSC: 68N17 68Q25 PDFBibTeX XMLCite \textit{H. Mannila} and \textit{E. Ukkonen}, BIT 30, No. 4, 599--619 (1990; Zbl 0746.68020) Full Text: DOI
Mourgues, M. H.; Ressayre, J. P. An application of Malcev’s series to polynomial time computability. (French) Zbl 0747.03033 Model theory, Proc. Sov.-Fr. Colloq., Karaganda/USSR 1990, 106-111 (1990). MSC: 03H15 03D15 PDFBibTeX XMLCite \textit{M. H. Mourgues} and \textit{J. P. Ressayre}, in: Les travaux scientifiques du colloque Sovieto-Francąis sur la théorie des modeles, Karaganda (USSR), 1990. Trudy sovetsko- francuzskogo kollokviuma po teorii modelej, Karaganda (SSSR), 1990. Karaganda: Karagandinskij Gosudarstvennyj Universitet. 106--111 (1990; Zbl 0747.03033)
Yanov, Yu. I. On lower bounds for the time of computation. (English. Russian original) Zbl 0790.68047 Discrete Math. Appl. 1, No. 4, 391-403 (1991); translation from Diskretn. Mat. 2, No. 1, 142-154 (1990). MSC: 68Q15 68Q05 PDFBibTeX XMLCite \textit{Yu. I. Yanov}, Discrete Math. Appl. 1, No. 4, 391--403 (1990; Zbl 0790.68047); translation from Diskretn. Mat. 2, No. 1, 142--154 (1990) Full Text: DOI
Eysselt, Miloš Time evaluation of three algorithms of multiplication. (Czech. English summary) Zbl 0792.68059 Knižnice, Odb. Věd. Spisů Vys. Uč. Tech., Brno, B 130, 225-237 (1990). MSC: 68Q25 PDFBibTeX XMLCite \textit{M. Eysselt}, Knižnice Odb. Věd. Spisů\ Vys. Uč. Tech., Brno, B 130, 225--237 (1990; Zbl 0792.68059)
Babai, László; Rónyai, Lajos Computing irreducible representations of finite groups. (English) Zbl 0760.20002 Math. Comput. 55, No. 192, 705-722 (1990). MSC: 20C15 20C40 68W30 PDFBibTeX XMLCite \textit{L. Babai} and \textit{L. Rónyai}, Math. Comput. 55, No. 192, 705--722 (1990; Zbl 0760.20002) Full Text: DOI
Brehgman, L. M. A polynomial-time simplex type method for solving linear systems of inequalities. (English. Russian original) Zbl 0754.65059 Cybernetics 26, No. 1, 106-110 (1990); translation from Kibernetika 1990, No. 1, 84-87 (1990). Reviewer: A.Roose (Tallinn) MSC: 65K05 65Y20 90C05 PDFBibTeX XMLCite \textit{L. M. Brehgman}, Cybernetics 26, No. 1, 106--110 (1990; Zbl 0754.65059); translation from Kibernetika 1990, No. 1, 84--87 (1990)
Sotskov, Yu. N. Complexity of optimal scheduling problems with three jobs. (English. Russian original) Zbl 0800.68212 Cybernetics 26, No. 5, 686-692 (1990); translation from Kibernetika 1990, No. 5, 50-54 (1990). MSC: 68M20 68Q25 PDFBibTeX XMLCite \textit{Yu. N. Sotskov}, Cybernetics 26, No. 5, 686--692 (1990; Zbl 0800.68212); translation from Kibernetika 1990, No. 5, 50--54 (1990) Full Text: DOI
Listrovoj, S. V. A parallel algorithm for the problem of shortest paths on a graph. (English. Russian original) Zbl 0749.05056 Sov. J. Comput. Syst. Sci. 29, No. 3, 60-66 (1991); translation from Izv. Akad. Nauk SSSR, Tekh. Kibern. 1990, No. 4, 189-196 (1990). Reviewer: Liu Zhenhong (Beijing) MSC: 05C85 68W15 05C38 90C39 PDFBibTeX XMLCite \textit{S. V. Listrovoj}, Sov. J. Comput. Syst. Sci. 29, No. 3, 60--66 (1990; Zbl 0749.05056); translation from Izv. Akad. Nauk SSSR, Tekh. Kibern. 1990, No. 4, 189--196 (1990)
Unger, Walter Colouring of chordal graphs. (Färbung von Kreissehnengraphen.) (German) Zbl 0762.05048 Paderborn: Univ. Paderborn, Fachb. Mathematik/Informatik, 175 S. (1990). Reviewer: C.Schulz (Wiesbaden) MSC: 05C15 68R10 68Q15 PDFBibTeX XMLCite \textit{W. Unger}, Färbung von Kreissehnengraphen. Paderborn: Univ. Paderborn, Fachb. Mathematik/Informatik (1990; Zbl 0762.05048)
Reischuk, Karl Rüdiger Einführung in die Komplexitätstheorie. (Introduction to complexity theory). (German) Zbl 0705.68053 Leitfäden und Monographien der Informatik. Stuttgart: B. G. Teubner. XVII, 412 p. DM 52.00 (1990). Reviewer: I.Wegener MSC: 68Q15 68Q25 03D15 68-01 68Q10 68Q05 PDFBibTeX XMLCite \textit{K. R. Reischuk}, Einführung in die Komplexitätstheorie. (Introduction to complexity theory). Stuttgart: B. G. Teubner (1990; Zbl 0705.68053)
Selman, Alan L. One-way functions in complexity theory. (English) Zbl 0733.68033 Mathematical foundations of computer science, Proc. 15th Symp., MFCS ’90, Banská Bystrica/Czech. 1990, Lect. Notes Comput. Sci. 452, 88-104 (1990). Reviewer: Du Ding-Zhu (Minneapolis) MSC: 68Q15 68-02 PDFBibTeX XML
Grädel, Erich On the notion of linear time computability. (English) Zbl 0732.68040 Int. J. Found. Comput. Sci. 1, No. 3, 295-307 (1990). MSC: 68Q15 68Q05 03D15 PDFBibTeX XMLCite \textit{E. Grädel}, Int. J. Found. Comput. Sci. 1, No. 3, 295--307 (1990; Zbl 0732.68040) Full Text: DOI
Kantor, William M. Finding Sylow normalizers in polynomial time. (English) Zbl 0731.20005 J. Algorithms 11, No. 4, 523-563 (1990). Reviewer: I.Janiszczak (Essen) MSC: 20B40 20D20 20B35 68Q25 PDFBibTeX XMLCite \textit{W. M. Kantor}, J. Algorithms 11, No. 4, 523--563 (1990; Zbl 0731.20005) Full Text: DOI Link
Joseph, Deborah; Sitharam, Meera Kolmogorov complexity, restricted nondeterminism and generalized spectra. (English) Zbl 0731.03024 Theoretical aspects of computer science, Proc. 7th Annu. Symp., STACS ’90, Rouen/Fr. 1990, Lect. Notes Comput. Sci. 415, 152-164 (1990). MSC: 03D15 68Q15 68Q30 PDFBibTeX XML
Lipton, Richard J. Efficient checking of computations. (English) Zbl 0729.68030 Theoretical aspects of computer science, Proc. 7th Annu. Symp., STACS ’90, Rouen/Fr. 1990, Lect. Notes Comput. Sci. 415, 207-215 (1990). MSC: 68Q25 PDFBibTeX XML
Allender, Eric; Beigel, Richard; Hertrampf, Ulrich; Homer, Steven A note on the almost-everywhere hierarchy for nondeterministic time. (English) Zbl 0729.68022 Theoretical aspects of computer science, Proc. 7th Annu. Symp., STACS ’90, Rouen/Fr. 1990, Lect. Notes Comput. Sci. 415, 1-11 (1990). MSC: 68Q15 PDFBibTeX XML
Kannan, Ravi Test sets for integer programs, \(\forall \exists\) sentences. (English) Zbl 0728.90062 Polyhedral combinatorics, Proc. Workshop, Morristown/NJ (USA) 1989, DIMACS, Ser. Discret. Math. Theor. Comput. Sci. 1, 39-47 (1990). Reviewer: R.Kannan MSC: 90C10 03D15 52B12 90C31 PDFBibTeX XML
Cook, W.; Hartmann, M. On the complexity of branch and cut methods for the traveling salesman problem. (English) Zbl 0727.90064 Polyhedral combinatorics, Proc. Workshop, Morristown/NJ (USA) 1989, DIMACS, Ser. Discret. Math. Theor. Comput. Sci. 1, 75-81 (1990). MSC: 90C27 90C60 90C35 PDFBibTeX XML
Benantar, Messaoud; Biswas, Rupak; Flaherty, Joseph E.; Shephard, Mark S. Parallel computation with adaptive methods for elliptic and hyperbolic systems. (English) Zbl 0727.73082 Comput. Methods Appl. Mech. Eng. 82, No. 1-3, 73-93 (1990). MSC: 74S05 65Y05 68R10 65N30 PDFBibTeX XMLCite \textit{M. Benantar} et al., Comput. Methods Appl. Mech. Eng. 82, No. 1--3, 73--93 (1990; Zbl 0727.73082) Full Text: DOI
Buchmann, Johannes A subexponential algorithm for the determination of class groups and regulators of algebraic number fields. (English) Zbl 0727.11059 Sémin. Théor. Nombres, Paris/Fr. 1988-89, Prog. Math. 91, 27-41 (1990). Reviewer: J.L.Hafner (San José) MSC: 11Y40 11R29 11Y16 68Q25 PDFBibTeX XML
Chakrabarty, N. R.; Chaudhuri, P. K. Geometric solution of a constrained rectilinear distance minimax location problem. (English) Zbl 0726.90045 Asia-Pac. J. Oper. Res. 7, No. 2, 163-171 (1990). MSC: 90B85 90C60 90-08 PDFBibTeX XMLCite \textit{N. R. Chakrabarty} and \textit{P. K. Chaudhuri}, Asia-Pac. J. Oper. Res. 7, No. 2, 163--171 (1990; Zbl 0726.90045)
Shi, Li An algorithm of scheduling in UET system for m processors and its performance analysis. (Chinese. English summary) Zbl 0726.90037 J. Southwest Jiaotong Univ. 1990, No. 4, 46-51 (1990). MSC: 90B35 90-08 90C60 PDFBibTeX XMLCite \textit{L. Shi}, J. Southwest Jiaotong Univ. 1990, No. 4, 46--51 (1990; Zbl 0726.90037)
Bishop, A. R. Competing interactions and complexity in condensed matter. (English) Zbl 0726.35105 Partially integrable evolution equations in physics, Proc. NATO/ASI, Les Houches/Fr. 1989, NATO ASI Ser., Ser. C 310, 1-38 (1990). MSC: 35Q40 35Q53 81V99 PDFBibTeX XML
Abhyankar, S. S.; Morin, T. L.; Trafalis, T. Efficient faces of polytopes: Interior point algorithms, parametrization of algebraic varieties, and multiple objective optimization. (English) Zbl 0725.90056 Mathematical developments arising from linear programming, Proc. AMS-IMS- SIAM Jt. Summer Res. Conf., Brunswick/ME (USA) 1988, Contemp. Math. 114, 319-341 (1990). MSC: 90C05 52B12 90C29 90-08 90C60 PDFBibTeX XML
Crama, Yves; Hansen, Pierre; Jaumard, Brigitte The basic algorithm for pseudo-Boolean programming revisited. (English) Zbl 0724.90040 Discrete Appl. Math. 29, No. 2-3, 171-185 (1990). Reviewer: I.Martinec (Praha) MSC: 90C09 90C60 90-08 90C30 PDFBibTeX XMLCite \textit{Y. Crama} et al., Discrete Appl. Math. 29, No. 2--3, 171--185 (1990; Zbl 0724.90040) Full Text: DOI
Yanov, Yu. I. On lower estimates of computation time. (Russian) Zbl 0724.68042 Diskretn. Mat. 2, No. 1, 142-154 (1990). MSC: 68Q15 68Q05 PDFBibTeX XMLCite \textit{Yu. I. Yanov}, Diskretn. Mat. 2, No. 1, 142--154 (1990; Zbl 0724.68042)
Pila, J. Frobenius maps of abelian varieties and finding roots of unity in finite fields. (English) Zbl 0724.11070 Math. Comput. 55, No. 192, 745-763 (1990). Reviewer: R.Schoof (Povo) MSC: 11Y16 14G15 68Q25 11G15 11G25 14K22 PDFBibTeX XMLCite \textit{J. Pila}, Math. Comput. 55, No. 192, 745--763 (1990; Zbl 0724.11070) Full Text: DOI
Ben-Daya, Mohamed; Shetty, C. M. Polynomial barrier function algorithms for convex quadratic programming. (English) Zbl 0723.90061 Arabian J. Sci. Eng. 15, No. 4B, 657-670 (1990). Reviewer: S.Mititelu (Bucureşti) MSC: 90C25 90C20 90-08 90C60 PDFBibTeX XML
Eissfeller, Horst; Müller, Silvia Melitta A note on reducing communication costs in explicit time stepping methods on parallel computers. (English) Zbl 0723.65068 Appl. Math. Comput. 39, No. 3, 191-197 (1990). Reviewer: G.Hedstrom (Livermore) MSC: 65M06 65Y05 65Y20 35K05 PDFBibTeX XMLCite \textit{H. Eissfeller} and \textit{S. M. Müller}, Appl. Math. Comput. 39, No. 3, 191--197 (1990; Zbl 0723.65068)
Berman, Oded Mean-variance location problems. (English) Zbl 0722.90041 Transp. Sci. 24, No. 4, 287-293 (1990). MSC: 90B80 90C60 PDFBibTeX XMLCite \textit{O. Berman}, Transp. Sci. 24, No. 4, 287--293 (1990; Zbl 0722.90041) Full Text: DOI
Burkard, R. E.; Rote, G.; Yao, E. Y.; Yu, Z. L. Shortest polygonal paths in space. (English) Zbl 0722.68098 Computing 45, No. 1, 51-68 (1990). MSC: 68U05 68Q25 90C25 PDFBibTeX XMLCite \textit{R. E. Burkard} et al., Computing 45, No. 1, 51--68 (1990; Zbl 0722.68098) Full Text: DOI
von zur Gathen, Joachim Functional decomposition of polynomials: the wild case. (English) Zbl 0722.12003 J. Symb. Comput. 10, No. 5, 437-452 (1990). Reviewer: Geert Molenberghs (Antwerpen) MSC: 12E05 12Y05 11Y16 68W10 68W30 11T06 PDFBibTeX XMLCite \textit{J. von zur Gathen}, J. Symb. Comput. 10, No. 5, 437--452 (1990; Zbl 0722.12003) Full Text: DOI
White, Douglas J. Heuristic programming. (English) Zbl 0721.90070 IMA J. Math. Appl. Bus. Ind. 2, No. 02, 173-188 (1990). Reviewer: D.J.White MSC: 90C30 90B50 90B99 90-08 90C60 91B06 PDFBibTeX XMLCite \textit{D. J. White}, IMA J. Math. Appl. Bus. Ind. 2, No. 02, 173--188 (1990; Zbl 0721.90070)
Bertsimas, Dimitris J.; Jaillet, Patrick; Odoni, Amedeo R. A priori optimization. (English) Zbl 0721.90062 Oper. Res. 38, No. 6, 1019-1033 (1990). MSC: 90C27 90C35 90B80 90C15 90-08 90C60 PDFBibTeX XMLCite \textit{D. J. Bertsimas} et al., Oper. Res. 38, No. 6, 1019--1033 (1990; Zbl 0721.90062) Full Text: DOI Link
Zimmermann, U. Search directions for a class of projective methods. (English) Zbl 0719.90046 Z. Oper. Res. 34, No. 5, 353-379 (1990). Reviewer: R.N.Kaul (Delhi) MSC: 90C05 90C60 90-08 PDFBibTeX XMLCite \textit{U. Zimmermann}, Z. Oper. Res. 34, No. 5, 353--379 (1990; Zbl 0719.90046) Full Text: DOI
Liu, Hai-Ning; Wrathall, C.; Zeger, Kenneth Efficient solution of some problems in free partially commutative monoids. (English) Zbl 0719.68036 Inf. Comput. 89, No. 2, 180-198 (1990). Reviewer: M.Steinby (Turku) MSC: 68Q45 68Q25 68R15 20M35 PDFBibTeX XMLCite \textit{H.-N. Liu} et al., Inf. Comput. 89, No. 2, 180--198 (1990; Zbl 0719.68036) Full Text: DOI
Schott, R. Combinatorial techniques in computer science. (English) Zbl 0719.68031 Bull. Soc. Math. Belg., Sér. B 42, No. 2, 141-155 (1990). MSC: 68Q25 68R05 PDFBibTeX XMLCite \textit{R. Schott}, Bull. Soc. Math. Belg., Sér. B 42, No. 2, 141--155 (1990; Zbl 0719.68031)
Józefowska, Joanna Scheduling unit-length two-machine flow shop under arbitrary precedence constraints. (English) Zbl 0718.90046 Belg. J. Oper. Res. Stat. Comput. Sci. 30, No. 2, 35-48 (1990). MSC: 90B35 90-08 90C60 PDFBibTeX XMLCite \textit{J. Józefowska}, Belg. J. Oper. Res. Stat. Comput. Sci. 30, No. 2, 35--48 (1990; Zbl 0718.90046)
Toda, Seinosuke Positive relativizations for log space computability. (English) Zbl 0718.68039 Theor. Comput. Sci. 77, No. 3, 221-235 (1990). Reviewer: G.Grigoras (Iaşi) MSC: 68Q15 03D15 68Q05 PDFBibTeX XMLCite \textit{S. Toda}, Theor. Comput. Sci. 77, No. 3, 221--235 (1990; Zbl 0718.68039) Full Text: DOI
Cai, Jin-yi; Hemachandra, Lane A. On the power of parity polynomial time. (English) Zbl 0718.68038 Math. Syst. Theory 23, No. 2, 95-106 (1990). MSC: 68Q15 03D15 68Q05 PDFBibTeX XMLCite \textit{J.-y. Cai} and \textit{L. A. Hemachandra}, Math. Syst. Theory 23, No. 2, 95--106 (1990; Zbl 0718.68038) Full Text: DOI
Balcázar, José L. Self-reducibility. (English) Zbl 0718.68037 J. Comput. Syst. Sci. 41, No. 3, 367-388 (1990). Reviewer: G.Grigoras (Iaşi) MSC: 68Q15 68Q45 03D15 PDFBibTeX XMLCite \textit{J. L. Balcázar}, J. Comput. Syst. Sci. 41, No. 3, 367--388 (1990; Zbl 0718.68037) Full Text: DOI
Chazelle, Bernard; Sharir, Micha An algorithm for generalized point location and its applications. (English) Zbl 0718.68029 J. Symb. Comput. 10, No. 3-4, 281-309 (1990). MSC: 68P15 68U05 68Q25 PDFBibTeX XMLCite \textit{B. Chazelle} and \textit{M. Sharir}, J. Symb. Comput. 10, No. 3--4, 281--309 (1990; Zbl 0718.68029) Full Text: DOI
Larsen, H. Legind; Yager, R. R. Efficient computation of transitive closures. (English) Zbl 0717.94020 Fuzzy Sets Syst. 38, No. 1, 81-90 (1990). Reviewer: W.Pedrycz MSC: 94D05 68Q25 PDFBibTeX XMLCite \textit{H. L. Larsen} and \textit{R. R. Yager}, Fuzzy Sets Syst. 38, No. 1, 81--90 (1990; Zbl 0717.94020) Full Text: DOI
Tseng, Paul Solving H-horizon, stationary Markov decision problems in time proportional to log (H). (English) Zbl 0717.90090 Oper. Res. Lett. 9, No. 5, 287-297 (1990). MSC: 90C40 90C39 90C60 90-08 PDFBibTeX XMLCite \textit{P. Tseng}, Oper. Res. Lett. 9, No. 5, 287--297 (1990; Zbl 0717.90090) Full Text: DOI
Simeone, B.; de Werra, Dominique; Cochand, M. Recognition of a class of unimodular functions. (English) Zbl 0717.90049 Discrete Appl. Math. 29, No. 2-3, 243-250 (1990); errata ibid. 32, No. 1, 77 (1991). MSC: 90C09 90-08 90C60 90C05 PDFBibTeX XMLCite \textit{B. Simeone} et al., Discrete Appl. Math. 29, No. 2--3, 243--250 (1990; Zbl 0717.90049) Full Text: DOI
Anthony, Martin H. G. Computing chromatic polynomials. (English) Zbl 0717.05035 Ars Comb. 29C, 216-220 (1990). Reviewer: M.Kubale MSC: 05C15 PDFBibTeX XMLCite \textit{M. H. G. Anthony}, Ars Comb. 29C, 216--220 (1990; Zbl 0717.05035)
Dutta, D.; Chaudhuri, P. K. A constrained minimax location problem for a circular region. (English) Zbl 0716.90070 Techniques in applied mathematics and applications. 65th birthday celebration of S. C. Dasgupta, Proc. Semin., Howrah/India 1988, 151-158 (1990). MSC: 90B85 90C60 PDFBibTeX XML
Dessouky, M. I.; Lageweg, B. J.; Lenstra, J. K.; van de Velde, S. L. Scheduling identical jobs on uniform parallel machines. (English) Zbl 0716.90053 Stat. Neerl. 44, No. 3, 115-123 (1990). MSC: 90B35 68M20 90C60 68Q25 68Q10 90C39 90-08 PDFBibTeX XMLCite \textit{M. I. Dessouky} et al., Stat. Neerl. 44, No. 3, 115--123 (1990; Zbl 0716.90053) Full Text: DOI
Nagamochi, Hiroshi; Ibaraki, Toshihide Multicommodity flows in certain planar directed networks. (English) Zbl 0716.90033 Discrete Appl. Math. 27, No. 1-2, 125-145 (1990). Reviewer: H.Kise MSC: 90B10 05C20 90C60 05C10 90C35 PDFBibTeX XMLCite \textit{H. Nagamochi} and \textit{T. Ibaraki}, Discrete Appl. Math. 27, No. 1--2, 125--145 (1990; Zbl 0716.90033) Full Text: DOI
O’Leary, D. P.; Stewart, G. W. Computing the eigenvalues and eigenvectors of symmetric arrowhead matrices. (English) Zbl 0716.65033 J. Comput. Phys. 90, No. 2, 497-505 (1990). Reviewer: S.Ząbek MSC: 65F15 65G50 65Y05 PDFBibTeX XMLCite \textit{D. P. O'Leary} and \textit{G. W. Stewart}, J. Comput. Phys. 90, No. 2, 497--505 (1990; Zbl 0716.65033) Full Text: DOI Link
Richey, Michael B. Optimal location of a path or tree on a network with cycles. (English) Zbl 0715.90071 Networks 20, No. 4, 391-407 (1990). MSC: 90B80 90C60 90C35 PDFBibTeX XMLCite \textit{M. B. Richey}, Networks 20, No. 4, 391--407 (1990; Zbl 0715.90071) Full Text: DOI
Błaźewicz, J.; Drozdowski, M.; Schmidt, G.; de Werra, Dominique Scheduling independent two processor tasks on a uniform duo-processor system. (English) Zbl 0715.90069 Discrete Appl. Math. 28, No. 1, 11-20 (1990). MSC: 90B35 68W15 90C60 PDFBibTeX XMLCite \textit{J. Błaźewicz} et al., Discrete Appl. Math. 28, No. 1, 11--20 (1990; Zbl 0715.90069) Full Text: DOI
Herrbach, Lee A.; Leung, Joseph Y.-T. Preemptive scheduling of equal length jobs on two machines to minimize mean flow time. (English) Zbl 0715.90064 Oper. Res. 38, No. 3, 487-494 (1990). MSC: 90B35 90C60 PDFBibTeX XMLCite \textit{L. A. Herrbach} and \textit{J. Y. T. Leung}, Oper. Res. 38, No. 3, 487--494 (1990; Zbl 0715.90064) Full Text: DOI
Masuzawa, Kaori; Mizuno, Shinji; Mori, Masao A polynomial time interior point algorithm for minimum cost flow problems. (English) Zbl 0715.90046 J. Oper. Res. Soc. Japan 33, No. 2, 157-167 (1990). Reviewer: K.G.Murty MSC: 90B10 90C35 90C60 90-08 PDFBibTeX XMLCite \textit{K. Masuzawa} et al., J. Oper. Res. Soc. Japan 33, No. 2, 157--167 (1990; Zbl 0715.90046) Full Text: DOI
Kleine Büning, Hans; Löwen, Ulrich Towards average complexity of propositional binary Prolog programs. (English) Zbl 0715.68039 Ann. Soc. Math. Pol., Ser. IV, Fundam. Inf. 13, No. 3, 387-399 (1990). Reviewer: S.P.Yukna MSC: 68Q25 68N17 PDFBibTeX XMLCite \textit{H. Kleine Büning} and \textit{U. Löwen}, Ann. Soc. Math. Pol., Ser. IV, Fundam. Inf. 13, No. 3, 387--399 (1990; Zbl 0715.68039)
Gavish, Bezalel; Johnson, Robert E. A fully polynomial approximation scheme for single-product scheduling in a finite capacity facility. (English) Zbl 0714.90050 Oper. Res. 38, No. 1, 70-83 (1990). Reviewer: H.Kise MSC: 90B30 90C39 90C60 90C90 90B35 PDFBibTeX XMLCite \textit{B. Gavish} and \textit{R. E. Johnson}, Oper. Res. 38, No. 1, 70--83 (1990; Zbl 0714.90050) Full Text: DOI
Veres, Sándor M. Relations between information criteria for model-structure selection. I: The role of Bayesian model order estimation. (English) Zbl 0713.62031 Int. J. Control 52, No. 2, 389-408 (1990). MSC: 62F15 62M10 62B10 62F10 PDFBibTeX XMLCite \textit{S. M. Veres}, Int. J. Control 52, No. 2, 389--408 (1990; Zbl 0713.62031) Full Text: DOI
Kaltofen, Erich; Trager, Barry M. Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators. (English) Zbl 0712.12001 J. Symb. Comput. 9, No. 3, 301-320 (1990). Reviewer: F. J. van der Linden (Eindhoven) MSC: 12-08 12D05 68W30 11C08 11Y16 PDFBibTeX XMLCite \textit{E. Kaltofen} and \textit{B. M. Trager}, J. Symb. Comput. 9, No. 3, 301--320 (1990; Zbl 0712.12001) Full Text: DOI
Padberg, M.; Rinaldi, G. An efficient algorithm for the minimum capacity cut problem. (English) Zbl 0711.90022 Math. Program., Ser. A 47, No. 1, 19-36 (1990). Reviewer: W.Li MSC: 90B10 90C35 90C60 PDFBibTeX XMLCite \textit{M. Padberg} and \textit{G. Rinaldi}, Math. Program. 47, No. 1 (A), 19--36 (1990; Zbl 0711.90022) Full Text: DOI
Lueker, George S.; Megiddo, Nimrod; Ramachandran, Vijaya Linear programming with two variables per inequality in poly-log time. (English) Zbl 0711.68063 SIAM J. Comput. 19, No. 6, 1000-1010 (1990). MSC: 68Q25 90C05 PDFBibTeX XMLCite \textit{G. S. Lueker} et al., SIAM J. Comput. 19, No. 6, 1000--1010 (1990; Zbl 0711.68063) Full Text: DOI Link
Grigoriev, Dima Yu.; Karpinski, Marek; Singer, Michael F. Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields. (English) Zbl 0711.68059 SIAM J. Comput. 19, No. 6, 1059-1063 (1990). MSC: 68W30 11T06 12Y05 11Y16 PDFBibTeX XMLCite \textit{D. Yu. Grigoriev} et al., SIAM J. Comput. 19, No. 6, 1059--1063 (1990; Zbl 0711.68059) Full Text: DOI Link
Bienstock, D. Linear-time test for small face covers in any fixed surface. (English) Zbl 0711.68056 SIAM J. Comput. 19, No. 5, 907-911 (1990). MSC: 68Q25 05C10 PDFBibTeX XMLCite \textit{D. Bienstock}, SIAM J. Comput. 19, No. 5, 907--911 (1990; Zbl 0711.68056) Full Text: DOI
Huang, Jau-Hsiung; Kleinrock, Leonard Distributed selectsort sorting algorithms on broadcast communication networks. (English) Zbl 0711.68053 Parallel Comput. 16, No. 2-3, 183-190 (1990). MSC: 68W15 68P10 68M10 PDFBibTeX XMLCite \textit{J.-H. Huang} and \textit{L. Kleinrock}, Parallel Comput. 16, No. 2--3, 183--190 (1990; Zbl 0711.68053) Full Text: DOI
Wagner, Klaus W. Bounded query classes. (English) Zbl 0711.68047 SIAM J. Comput. 19, No. 5, 833-846 (1990). MSC: 68Q15 03D15 PDFBibTeX XMLCite \textit{K. W. Wagner}, SIAM J. Comput. 19, No. 5, 833--846 (1990; Zbl 0711.68047) Full Text: DOI
Lutz, Jack H. Category and measure in complexity classes. (English) Zbl 0711.68046 SIAM J. Comput. 19, No. 6, 1100-1131 (1990). MSC: 68Q15 03D15 68Q30 PDFBibTeX XMLCite \textit{J. H. Lutz}, SIAM J. Comput. 19, No. 6, 1100--1131 (1990; Zbl 0711.68046) Full Text: DOI
Grädel, Erich Domino games and complexity. (English) Zbl 0711.68044 SIAM J. Comput. 19, No. 5, 787-804 (1990). MSC: 68Q15 03D15 68Q05 91A05 PDFBibTeX XMLCite \textit{E. Grädel}, SIAM J. Comput. 19, No. 5, 787--804 (1990; Zbl 0711.68044) Full Text: DOI
Devroye, Luc; Laforest, Louise An analysis of random \(d\)-dimensional quad trees. (English) Zbl 0711.68032 SIAM J. Comput. 19, No. 5, 821-832 (1990). MSC: 68P05 68Q25 PDFBibTeX XMLCite \textit{L. Devroye} and \textit{L. Laforest}, SIAM J. Comput. 19, No. 5, 821--832 (1990; Zbl 0711.68032) Full Text: DOI
Posner, Marc E. Reducibility among single machine weighted completion time scheduling problems. (English) Zbl 0709.90065 Ann. Oper. Res. 26, 91-101 (1990). MSC: 90B35 90C60 PDFBibTeX XMLCite \textit{M. E. Posner}, Ann. Oper. Res. 26, 91--101 (1990; Zbl 0709.90065) Full Text: DOI
Lawler, E. L A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs. (English) Zbl 0709.90064 Ann. Oper. Res. 26, 125-133 (1990). MSC: 90B35 90C39 90C60 PDFBibTeX XMLCite \textit{E. L Lawler}, Ann. Oper. Res. 26, 125--133 (1990; Zbl 0709.90064) Full Text: DOI
Bulgak, A. S. Problem of parallel machines with polymatroidal constraints. (English. Russian original) Zbl 0709.90058 Autom. Remote Control 51, No. 3, 375-381 (1990); translation from Avtom. Telemekh. 1990, No. 3, 118-126 (1990). MSC: 90B35 90C60 90-08 PDFBibTeX XMLCite \textit{A. S. Bulgak}, Autom. Remote Control 51, No. 3, 375--381 (1990; Zbl 0709.90058); translation from Avtom. Telemekh. 1990, No. 3, 118--126 (1990)
Weiss, Mark Allen; Sedgewick, Robert Tight lower bounds for Shellsort. (English) Zbl 0709.68016 J. Algorithms 11, No. 2, 242-251 (1990). Reviewer: J.Vyskoc MSC: 68P10 68Q25 PDFBibTeX XMLCite \textit{M. A. Weiss} and \textit{R. Sedgewick}, J. Algorithms 11, No. 2, 242--251 (1990; Zbl 0709.68016) Full Text: DOI
Stepanov, S. A.; Shparlinskij, I. E. On the construction of a primitive normal basis in a finite field. (English. Russian original) Zbl 0709.11073 Math. USSR, Sb. 67, No. 2, 527-533 (1990); translation from Mat. Sb. 180, No. 8, 1067-1072 (1989). MSC: 11T30 11T06 11Y16 PDFBibTeX XMLCite \textit{S. A. Stepanov} and \textit{I. E. Shparlinskij}, Math. USSR, Sb. 67, No. 2, 527--533 (1990; Zbl 0709.11073); translation from Mat. Sb. 180, No. 8, 1067--1072 (1989) Full Text: DOI
Chen, Jian-er The difference between one tape and two tapes: With respect to reversal complexity. (English) Zbl 0709.03033 Theor. Comput. Sci. 73, No. 3, 265-278 (1990). Reviewer: D.Lucanu MSC: 03D15 03D10 68Q05 68Q15 PDFBibTeX XMLCite \textit{J.-e. Chen}, Theor. Comput. Sci. 73, No. 3, 265--278 (1990; Zbl 0709.03033) Full Text: DOI
Vaidya, Pravin M. An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations. (English) Zbl 0708.90047 Math. Program., Ser. A 47, No. 2, 175-201 (1990). Reviewer: J.Rohn MSC: 90C05 90C60 52B12 PDFBibTeX XMLCite \textit{P. M. Vaidya}, Math. Program. 47, No. 2 (A), 175--201 (1990; Zbl 0708.90047) Full Text: DOI
Lu, Hao On computational complexity for the multiplication of generalized Hilbert matrices with vectors and solution of certain generalized linear Hilbert systems. (English) Zbl 0708.65042 Chin. Sci. Bull. 35, No. 12, 974-978 (1990). Reviewer: Prem Narain (Faridabad) MSC: 65F30 65F05 65Y20 PDFBibTeX XMLCite \textit{H. Lu}, Chin. Sci. Bull. 35, No. 12, 974--978 (1990; Zbl 0708.65042)
Grigorieff, Serge Every recursive linear ordering has a copy in DTIME-SPACE(n,log(n)). (English) Zbl 0708.03015 J. Symb. Log. 55, No. 1, 260-276 (1990). Reviewer: Tao Renji MSC: 03D15 68Q15 PDFBibTeX XMLCite \textit{S. Grigorieff}, J. Symb. Log. 55, No. 1, 260--276 (1990; Zbl 0708.03015) Full Text: DOI
Book, Ronald V.; Tang, Shouwen Characterizing polynomial complexity classes by reducibilities. (English) Zbl 0707.68035 Math. Syst. Theory 23, No. 3, 165-174 (1990). MSC: 68Q15 03D15 PDFBibTeX XMLCite \textit{R. V. Book} and \textit{S. Tang}, Math. Syst. Theory 23, No. 3, 165--174 (1990; Zbl 0707.68035) Full Text: DOI
Bottura, Celso P.; Costa Filho, José T. On parallel programming environments and multilevel optimization. (English) Zbl 0707.65041 System modelling and optimization, Proc. 14th IFIP Conf., Leipzig/GDR 1989, Lect. Notes Control Inf. Sci. 143, 84-93 (1990). Reviewer: N.Djuranović-Miličić MSC: 65K05 90C30 65Y05 65Y10 65Y20 PDFBibTeX XML
Maass, Wolfgang; Slaman, Theodore A. On the relationship between the complexity, the degree, and the extension of a computable set. (English) Zbl 0707.03033 Recursion theory week, Proc. Conf., Oberwolfach/FRG 1989, Lect. Notes Math. 1432, 297-322 (1990). Reviewer: D.Mundici MSC: 03D15 03D25 68Q15 PDFBibTeX XML
Ferreira, Fernando Polynomial time computable arithmetic. (English) Zbl 0707.03032 Logic and computation, Proc. Workshop, Pittsburgh/PA (USA) 1987, Contemp. Math. 106, 137-156 (1990). Reviewer: M.Tetruashvili MSC: 03D15 03F30 PDFBibTeX XML
Inoue, Katsushi; Takanami, Itsuo A note on time-bounded bottom-up pyramid cellular acceptors. (English) Zbl 0706.68078 Inf. Sci. 51, No. 2, 121-133 (1990). MSC: 68Q80 03D15 68Q45 PDFBibTeX XMLCite \textit{K. Inoue} and \textit{I. Takanami}, Inf. Sci. 51, No. 2, 121--133 (1990; Zbl 0706.68078) Full Text: DOI
Rubinfeld, Ronitt The cover time of a regular expander is O(n log n). (English) Zbl 0706.68059 Inf. Process. Lett. 35, No. 1, 49-51 (1990). MSC: 68Q25 68R10 03D15 05A99 PDFBibTeX XMLCite \textit{R. Rubinfeld}, Inf. Process. Lett. 35, No. 1, 49--51 (1990; Zbl 0706.68059) Full Text: DOI
Sheu, Jang-Ping; Chiang, Zen-Fu Efficient allocation of chain-like task on chain-like network computers. (English) Zbl 0706.68017 Inf. Process. Lett. 36, No. 5, 241-245 (1990). MSC: 68M10 68W15 68Q25 PDFBibTeX XMLCite \textit{J.-P. Sheu} and \textit{Z.-F. Chiang}, Inf. Process. Lett. 36, No. 5, 241--245 (1990; Zbl 0706.68017) Full Text: DOI
Neumann, Klaus Min-sum and min-max single-machine scheduling with stochastic tree-like precedence constraints: Complexity and algorithms. (English) Zbl 0705.90035 System modelling and optimization, Proc. 14th IFIP Conf., Leipzig/GDR 1989, Lect. Notes Control Inf. Sci. 143, 501-509 (1990). Reviewer: J.Rohn MSC: 90B35 90C60 60G99 PDFBibTeX XML
Nerode, A.; Remmel, J. B. Polynomially isolated sets. (English) Zbl 0705.03024 Recursion theory week, Proc. Conf., Oberwolfach/FRG 1989, Lect. Notes Math. 1432, 323-362 (1990). Reviewer: L.Harkleroad MSC: 03D50 03D15 PDFBibTeX XML
Bruck, Jehoshua; Naor, Moni The hardness of decoding linear codes with preprocessing. (English) Zbl 0704.94022 IEEE Trans. Inf. Theory 36, No. 2, 381-385 (1990). MSC: 94B35 PDFBibTeX XMLCite \textit{J. Bruck} and \textit{M. Naor}, IEEE Trans. Inf. Theory 36, No. 2, 381--385 (1990; Zbl 0704.94022) Full Text: DOI Link
Martin, Alexander A polynomially solvable case of the separation problem for the Steiner- partition inequalities. (English) Zbl 0704.90077 Operations research, Proc. 14th Symp., Ulm/FRG 1989, Methods Oper. Res. 62, 277-284 (1990). Reviewer: A.Martin MSC: 90C27 90C35 90C60 90-08 90C39 68W35 PDFBibTeX XML
Chang, R. S.; Lee, R. C. T. On the continuous working problem. (English) Zbl 0704.90047 Discrete Appl. Math. 28, No. 2, 93-109 (1990). MSC: 90B35 90C60 90-08 90C27 PDFBibTeX XMLCite \textit{R. S. Chang} and \textit{R. C. T. Lee}, Discrete Appl. Math. 28, No. 2, 93--109 (1990; Zbl 0704.90047) Full Text: DOI
Paulik, A. Worst-case analysis of a generalized heapsort algorithm. (English) Zbl 0704.68056 Inf. Process. Lett. 36, No. 3, 159-165 (1990). MSC: 68Q25 68P10 PDFBibTeX XMLCite \textit{A. Paulik}, Inf. Process. Lett. 36, No. 3, 159--165 (1990; Zbl 0704.68056) Full Text: DOI
Canny, John Generalised characteristic polynomials. (English) Zbl 0704.12004 J. Symb. Comput. 9, No. 3, 241-250 (1990). Reviewer: D.Stefănescu MSC: 12E05 68W10 12Y05 68Q25 PDFBibTeX XMLCite \textit{J. Canny}, J. Symb. Comput. 9, No. 3, 241--250 (1990; Zbl 0704.12004) Full Text: DOI
Allender, Eric; Watanabe, Osamu Kolmogorov complexity and degrees of tally sets. (English) Zbl 0704.03023 Inf. Comput. 86, No. 2, 160-178 (1990). Reviewer: Gheorghe Grigoras (Iaşi) MSC: 03D15 68Q15 68Q30 PDFBibTeX XMLCite \textit{E. Allender} and \textit{O. Watanabe}, Inf. Comput. 86, No. 2, 160--178 (1990; Zbl 0704.03023) Full Text: DOI
Hellerstein, Lisa; Klein, Philip; Wilber, Robert On the time-space complexity of reachability queries for preprocessed graphs. (English) Zbl 0703.68061 Inf. Process. Lett. 35, No. 5, 261-267 (1990). MSC: 68Q25 68R10 PDFBibTeX XMLCite \textit{L. Hellerstein} et al., Inf. Process. Lett. 35, No. 5, 261--267 (1990; Zbl 0703.68061) Full Text: DOI
Kim, Sung Kwon Parallel algorithms for planar dominance counting. (English) Zbl 0703.68051 Parallel Comput. 15, No. 1-3, 241-246 (1990). MSC: 68W15 68U05 68Q25 PDFBibTeX XMLCite \textit{S. K. Kim}, Parallel Comput. 15, No. 1--3, 241--246 (1990; Zbl 0703.68051) Full Text: DOI
Baum, Eric B. On learning a union of half spaces. (English) Zbl 0702.68089 J. Complexity 6, No. 1, 67-101 (1990). MSC: 68T05 68Q25 PDFBibTeX XMLCite \textit{E. B. Baum}, J. Complexity 6, No. 1, 67--101 (1990; Zbl 0702.68089) Full Text: DOI
Cook, Stephen; Pitassi, Toniann A feasibly constructive lower bound for resolution proofs. (English) Zbl 0702.68065 Inf. Process. Lett. 34, No. 2, 81-85 (1990). MSC: 68Q25 68T15 PDFBibTeX XMLCite \textit{S. Cook} and \textit{T. Pitassi}, Inf. Process. Lett. 34, No. 2, 81--85 (1990; Zbl 0702.68065) Full Text: DOI
Psaraftis, Harilaos N.; Solomon, Marius M.; Magnanti, Thomas L.; Kim, Tai-Up Routing and scheduling on a shoreline with release times. (English) Zbl 0701.90050 Manage. Sci. 36, No. 2, 212-223 (1990). Reviewer: M.Kubale MSC: 90B35 90C60 90C39 65K05 90B06 90-08 PDFBibTeX XMLCite \textit{H. N. Psaraftis} et al., Manage. Sci. 36, No. 2, 212--223 (1990; Zbl 0701.90050) Full Text: DOI Link
Casas, Rafael; Fernández-Camacho, María-Inés; Steyaert, Jean- Marc Algebraic simplification in computer algebra: an analysis of bottom-up algorithms. (English) Zbl 0701.68045 Theor. Comput. Sci. 74, No. 3, 273-298 (1990). MSC: 68Q25 68W30 PDFBibTeX XMLCite \textit{R. Casas} et al., Theor. Comput. Sci. 74, No. 3, 273--298 (1990; Zbl 0701.68045) Full Text: DOI
Hertrampf, Ulrich Relations among MOD-classes. (English) Zbl 0701.68029 Theor. Comput. Sci. 74, No. 3, 325-328 (1990). MSC: 68Q15 03D15 PDFBibTeX XMLCite \textit{U. Hertrampf}, Theor. Comput. Sci. 74, No. 3, 325--328 (1990; Zbl 0701.68029) Full Text: DOI
Hartmanis, Juris; Hemachandra, Lane A. Robust machines accept easy sets. (English) Zbl 0701.68028 Theor. Comput. Sci. 74, No. 2, 217-225 (1990). MSC: 68Q15 68Q05 PDFBibTeX XMLCite \textit{J. Hartmanis} and \textit{L. A. Hemachandra}, Theor. Comput. Sci. 74, No. 2, 217--225 (1990; Zbl 0701.68028) Full Text: DOI
Nerode, A.; Remmel, J. B. Polynomial time equivalence types. (English) Zbl 0701.03017 Logic and computation, Proc. Workshop, Pittsburgh/PA (USA) 1987, Contemp. Math. 106, 221-249 (1990). Reviewer: R.Downey MSC: 03D15 03D50 68Q15 PDFBibTeX XML