%%% -*-BibTeX-*- %%% ==================================================================== %%% BibTeX-file{ %%% author = "Nelson H. F. Beebe", %%% version = "2.01", %%% date = "03 April 2006", %%% time = "10:35:38 MST", %%% filename = "siamjcomput.bib", %%% address = "University of Utah %%% Department of Mathematics, 110 LCB %%% 155 S 1400 E RM 233 %%% Salt Lake City, UT 84112-0090 %%% USA", %%% telephone = "+1 801 581 5254", %%% FAX = "+1 801 581 4148", %%% URL = "http://www.math.utah.edu/~beebe", %%% checksum = "23841 40540 149440 1436728", %%% email = "beebe at math.utah.edu, beebe at acm.org, %%% beebe at computer.org (Internet)", %%% codetable = "ISO/ASCII", %%% keywords = "BibTeX; bibliography; SIAM Journal on %%% Computing; SICOMP", %%% license = "public domain", %%% supported = "yes", %%% docstring = "This is a bibliography of publications in %%% the SIAM Journal on Computing (CODEN %%% SMJCAT, ISSN 0097-5397 (print), 1095-7111 %%% (electronic)), which began publishing in %%% 1972. %%% %%% NB: Since the SIAM journals introduced %%% electronic prepublication in the late 1990s, %%% the volume/year relationships have become %%% blurred, because the SIAM Web %%% tables-of-contents files do not record the %%% publication year. I am working with SIAM to %%% find a solution to this problem. %%% %%% At version 2.00 of this bibliography, all %%% article Web pages have been downloaded and %%% used to correct blurry publication years, %%% and Digital Object Identifier (DOI) values %%% have been added when available. %%% %%% The journal has World Wide Web sites at %%% %%% http://epubs.siam.org/sam-bin/dbq/toclist/SICOMP %%% http://www.siam.org/journals/sicomp.htm %%% http://www.siam.org/journals/sicomp/sicomp.htm %%% http://www.siam.org/sam-bin/dbg/toclist/SICOMP %%% %%% with editorial and publication information, %%% and pointers to tables of contents of recent %%% issues. %%% %%% Data for earlier volumes (1972--1996) is %%% available at: %%% %%% http://locus.siam.org/SICOMP/sicomp_toc.html %%% %%% At version 2.01, the year coverage looked %%% like this: %%% %%% 1972 ( 2) 1984 ( 55) 1996 ( 62) %%% 1973 ( 10) 1985 ( 73) 1997 ( 84) %%% 1974 ( 2) 1986 ( 81) 1998 ( 131) %%% 1975 ( 7) 1987 ( 73) 1999 ( 115) %%% 1976 ( 9) 1988 ( 79) 2000 ( 119) %%% 1977 ( 10) 1989 ( 84) 2001 ( 45) %%% 1978 ( 20) 1990 ( 77) 2002 ( 61) %%% 1979 ( 52) 1991 ( 72) 2003 ( 74) %%% 1980 ( 64) 1992 ( 71) 2004 ( 78) %%% 1981 ( 63) 1993 ( 81) 2005 ( 53) %%% 1982 ( 63) 1994 ( 79) %%% 1983 ( 53) 1995 ( 79) %%% %%% Article: 2081 %%% %%% Total entries: 2081 %%% %%% The initial draft of entries for 1990--1996 %%% was derived from the OCLC Contents1st %%% database. Additions were then made from %%% all of the bibliographies in the TeX User %%% Group collection, from bibliographies in %%% the author's personal files, from the %%% MathSciNet database, and from the computer %%% science bibliography collection on %%% ftp.ira.uka.de in /pub/bibliography to %%% which many people of have contributed. The %%% snapshot of this collection was taken on %%% 5-May-1994, and it consists of 441 BibTeX %%% files, 2,672,675 lines, 205,289 entries, %%% and 6,375 String{} abbreviations, %%% occupying 94.8MB of disk space. %%% %%% Numerous errors in the sources noted above %%% have been corrected. Spelling has been %%% verified with the UNIX spell and GNU ispell %%% programs using the exception dictionary %%% stored in the companion file with extension %%% .sok. %%% %%% BibTeX citation tags are uniformly chosen %%% as name:year:abbrev, where name is the %%% family name of the first author or editor, %%% year is a 4-digit number, and abbrev is a %%% 3-letter condensation of important title %%% words. Citation tags were automatically %%% generated by software developed for the %%% BibNet Project. %%% %%% In this bibliography, entries are sorted in %%% publication order within each journal, %%% using bibsort -byvolume. %%% %%% The checksum field above contains a CRC-16 %%% checksum as the first value, followed by the %%% equivalent of the standard UNIX wc (word %%% count) utility output of lines, words, and %%% characters. This is produced by Robert %%% Solovay's checksum utility.", %%% } %%% ==================================================================== @Preamble{ "\ifx \mathbb \undefined \def \mathbb #1{{\bf #1}}\fi" } %%% ==================================================================== %%% Acknowledgement abbreviations: @String{ack-nhfb = "Nelson H. F. Beebe, University of Utah, Department of Mathematics, 110 LCB, 155 S 1400 E RM 233, Salt Lake City, UT 84112-0090, USA, Tel: +1 801 581 5254, FAX: +1 801 581 4148, e-mail: \path|beebe@math.utah.edu|, \path|beebe@acm.org|, \path|beebe@computer.org| (Internet), URL: \path|http://www.math.utah.edu/~beebe/|"} %%% ==================================================================== %%% Journal abbreviations: @String{j-SIAM-J-COMPUT = "SIAM Journal on Computing"} %%% ==================================================================== %%% Bibliography entries. %%% Early volumes: issue 1=mar, 2=jun, 3=sep, 4=dec @Article{Tarjan:1972:DFS, author = "R. E. Tarjan", key = "Tarjan", title = "Depth First Search and Linear Graph Algorithms", journal = j-SIAM-J-COMPUT, volume = "1", number = "2", pages = "146--160", month = jun, year = "1972", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibdate = "Thu Jan 23 09:56:44 1997", bibsource = "Parallel/Multi.bib, Misc/Reverse.eng.bib", } @Article{Hecht:1972:FGR, author = "M. S. Hecht and J. D. Ullman", title = "Flow Graph Reducibility", journal = j-SIAM-J-COMPUT, volume = "1", number = "2", pages = "188--202", month = jun, year = "1972", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibdate = "Thu Apr 9 08:03:57 1998", bibsource = "Compiler/optimization.bib, Compiler/opt.compiler.bib", } @Article{Nievergelt:1973:BST, author = "J. Nievergelt and E. M. Reingold", title = "Binary Search Trees of Bounded Balance", journal = j-SIAM-J-COMPUT, volume = "2", number = "1", pages = "33--43", month = mar, year = "1973", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibdate = "Thu Jan 23 10:31:35 1997", bibsource = "Database/Wiederhold.bib", } @Article{Paterson:1973:NNM, author = "M. S. Paterson and L. J. Stockmeyer", title = "On the Number of Nonscalar Multiplications Necessary to Evaluate Polynomials", journal = j-SIAM-J-COMPUT, volume = "2", number = "1", pages = "60--66", month = mar, year = "1973", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibdate = "Thu Jan 23 09:58:15 1997", bibsource = "Theory/Matrix.bib", note = "Cited in \cite{govl:89}.", kwds = "na, polynomial, complexity", } @Article{Holland:1973:GAO, author = "J. H. Holland", key = "genetic-algorithms", title = "Genetic Algorithms and the Optimal Allocation of Trials", journal = j-SIAM-J-COMPUT, volume = "2", number = "2", pages = "88--105", month = apr, year = "1973", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibdate = "Thu Apr 09 08:08:35 1998", bibsource = "Misc/misc.1.bib, Ai/alife.bib", abstract = "This study gives a formal setting to the difficult optimisation problems characterised by the conjunction of (1) substantial complexity and initial uncertainty, (2) the necessity of acquiring new information rapidly to reduce the uncertainty and (3) a requirement that the new information be exploited as acquired so that average performance increases at a rate consistent with th rate of acquisition of information. The setting has as its basis a set A of structures to be searched or tried and a performance function u:A->real numbers. Within this setting it is determined how to allocate trials to a set of random variables so as to maximise expected performances. This result is then transformed into a critereon against which to measure the performance of a robust and easily implemented set of algorithms called reproductive plans. It is shown that reproductive plans can in fact surpass the critereon because of a phenomenon called intrinsic parallelism - a single trial (individual a E A) simultaneously tests and exploits many random variables.", annote = "A mathematical analysis of genetic algorithms and their ``implicit parallelism''.", } @Article{Hopcroft:1973:DAC, author = "J. E. Hopcroft and J. Musinski", key = "Hopcroft \& Musinski", title = "Duality Applied to the Complexity of Matrix Multiplications and Other Bilinear Forms", journal = j-SIAM-J-COMPUT, volume = "2", number = "2", pages = "159--173", month = apr, year = "1973", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibdate = "Thu Apr 09 08:08:41 1998", bibsource = "Parallel/Multi.bib", } @Article{Hopcroft:1973:DGT, author = "J. E. Hopcroft and R. E. Tarjan", key = "Hopcroft \& Tarjan", title = "Dividing a Graph into Triconnected Components", journal = j-SIAM-J-COMPUT, volume = "2", number = "3", pages = "135--158", month = aug, year = "1973", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibsource = "Parallel/Multi.bib, Misc/Reverse.eng.bib", } @Article{Hopcroft:1973:AMM, author = "John E. Hopcroft and Richard M. Karp", title = "An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs", journal = j-SIAM-J-COMPUT, volume = "2", number = "4", pages = "225--231", month = dec, year = "1973", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibdate = "Thu Jan 23 09:57:46 1997", bibsource = "Database/Wiederhold.bib", } @Article{Lavenberg:1973:QAM, author = "Stephen S. Lavenberg", title = "Queuing Analysis of a Multiprogrammed Computer System Having a Multi-level Storage Hierarchy", journal = j-SIAM-J-COMPUT, volume = "2", number = "4", pages = "232--252", month = dec, year = "1973", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibdate = "Thu Jan 23 10:31:59 1997", bibsource = "Database/Wiederhold.bib", note = "Also published in/as: IBM Res.R. RJ1133, Nov.1972.", } @Article{McRae:1973:AER, author = "Walter B. McRae and Ernest R. Davidson", title = "An algorithm for the extreme rays of a pointed convex polyhedral cone", journal = j-SIAM-J-COMPUT, volume = "2", number = "4", pages = "281--293", month = dec, year = "1973", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibdate = "Thu Jan 23 10:31:19 1997", bibsource = "Graphics/siggraph/pre75.bib", oldlabel = "geom-3074", } @Article{Hopcroft:1973:SMA, author = "J. E. Hopcroft and J. D. Ullman", key = "Hopcroft \& Ullman", title = "Set Merging Algorithms", journal = j-SIAM-J-COMPUT, volume = "2", number = "4", pages = "294--303", month = dec, year = "1973", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibsource = "Parallel/Multi.bib", } @Article{Corneil:1973:ADC, author = "D. G. Corneil and B. Graham", title = "An algorithm for determining the chromatic number of a graph", journal = j-SIAM-J-COMPUT, volume = "2", number = "4", pages = "311--218", month = dec, year = "1973", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibdate = "Thu Jan 23 10:31:24 1997", bibsource = "Theory/clique.color.bib", annote = "Implicit enumeration algorithm based on Zykov's theorem.", } @Article{Fateman:1974:PMP, author = "Richard J. Fateman", title = "Polynomial Multiplication, Powers, and asymptotic Analysis: {Some} Comments", journal = j-SIAM-J-COMPUT, volume = "3", number = "3", pages = "196--213", month = "????", year = "1974", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibdate = "Thu Jan 23 10:32:27 1997", bibsource = "Theory/Comp.Alg.1.bib, Theory/auto.diff.bib", referred = "[Bren78a].", } @Article{Johnson:1974:WCP, author = "D. S. Johnson and A. Demers and J. D. Ullman and M. R. Garey and R. L. Graham", title = "Worst-case Performance Bounds for Simple One-dimensional Packing Algorithms", journal = j-SIAM-J-COMPUT, volume = "3", number = "4", pages = "299--325", month = dec, year = "1974", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibdate = "Thu Jan 23 10:32:28 1997", bibsource = "Database/Wiederhold.bib", } @Article{Miller:1975:CCN, author = "Webb Miller", key = "Miller", title = "Computational Complexity and Numerical Stability", journal = j-SIAM-J-COMPUT, volume = "4", number = "2", pages = "97--107", month = jun, year = "1975", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibdate = "Thu Jan 23 10:34:21 1997", bibsource = "Parallel/Multi.bib, Theory/Matrix.bib", kwds = "na, rounding error, complexity", } @Article{Lavenberg:1975:DCI, author = "S. S. Lavenberg and G. S. Shedler", title = "Derivation of Confidence Intervals for Work Rate Estimators in a Closed Queueing Network", journal = j-SIAM-J-COMPUT, volume = "4", number = "2", pages = "108--124", month = jun, year = "1975", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibdate = "Thu Apr 9 08:04:36 1998", bibsource = "Distributed/QLD/1975.bib", annote = "(VBI-000440)", country = "USA", date = "01/07/93", descriptors = "Closed queueing network; confidence interval;", enum = "10354", language = "English", references = "0", town = "Philadephia", } @Article{Kuck:1975:TBP, author = "D. Kuck and K. Maruyama", key = "Kuck \& Maruyama", title = "Time Bounds on the Parallel Evaluation of Arithmetic Expressions", journal = j-SIAM-J-COMPUT, volume = "4", number = "2", pages = "147--162", month = jun, year = "1975", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibsource = "Parallel/Multi.bib", } @Article{Hall:1975:SPE, author = "Andrew D. {Hall, Jr.}", title = "Solving a problem in eigenvalue approximation with a symbolic algebra system", journal = j-SIAM-J-COMPUT, volume = "4", pages = "163--174", year = "1975", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68A15 (65L15)", MRnumber = "MR0378468 (51 \#14636)", MRreviewer = "Bernard H. Rosman", fjournal = "SIAM Journal on Computing", } @Article{Strong:1975:RSS, author = "H. R. A. Strong and A. Maggiolo-Schettini and B. A. Rosen", title = "Recusion Structure Simplification", journal = j-SIAM-J-COMPUT, volume = "4", number = "3", pages = "307--320", month = "????", year = "1975", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibsource = "Compiler/opt.compiler.bib, Compiler/optimization.bib", } @Article{Rosenberg:1975:PPA, author = "Arnold L. Rosenberg", title = "Preserving Proximity in Arrays", journal = j-SIAM-J-COMPUT, volume = "4", number = "4", pages = "443--460", month = dec, year = "1975", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibdate = "Sat Jan 18 15:06:19 1997", bibsource = "ftp://ftp.ira.uka.de/pub/bibliography/Theory/partition.bib", } @Article{Even:1975:NFT, author = "Shimon Even and R. Endre Tarjan", key = "Even \& Tarjan", title = "Network Flow and Testing Graph Connectivity", journal = j-SIAM-J-COMPUT, volume = "4", number = "4", pages = "507--518", month = dec, year = "1975", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibdate = "Thu Jan 23 10:34:19 1997", bibsource = "Parallel/Multi.bib", } @Article{Rivest:1976:PMR, author = "R. L. Rivest", title = "Partial Match Retrieval Algorithms", journal = j-SIAM-J-COMPUT, volume = "5", number = "1", pages = "19--50", month = "????", year = "1976", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibdate = "Thu Jan 23 10:46:30 1997", bibsource = "Database/Wiederhold.bib", } @Article{Dobkin:1976:MSP, author = "D. P. Dobkin and R. J. Lipton", key = "Dobkin \& Lipton", title = "Multidimensional searching problems", journal = j-SIAM-J-COMPUT, volume = "5", number = "2", pages = "181--186", month = jun, year = "1976", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibsource = "Graphics/siggraph/76.bib, Parallel/Multi.bib", oldlabel = "geom-158", } @Article{Ashcroft:1976:LAF, author = "E. A. Ashcroft and W. W. Wadge", title = "Lucid --- {A} Formal System for Writing and Proving", journal = j-SIAM-J-COMPUT, volume = "5", number = "3", pages = "336--354", month = sep, year = "1976", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibsource = "Misc/Functional.bib, Compiler/semantics.bib", keywords = "functional languages", } @Article{Downey:1976:CCR, author = "Peter J. Downey and Ravi Sethi", title = "Correct Computation Rules for Recursive Languages", journal = j-SIAM-J-COMPUT, volume = "5", number = "3", pages = "378--401", month = sep, year = "1976", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibdate = "Thu Jan 23 10:34:16 1997", bibsource = "Misc/Functional.bib", keywords = "functional", } @Article{Manna:1976:TAO, author = "Zohar Manna and Adi Shamir", title = "The Theoretical Aspects of the Optimal {FixedPoint}", journal = j-SIAM-J-COMPUT, volume = "5", number = "3", pages = "414--426", month = sep, year = "1976", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibdate = "Tue Jan 28 11:55:27 1997", bibsource = "Compiler/semantics.bib", } @Article{Wadsworth:1976:RBC, author = "Christopher P. Wadsworth", key = "Wadsworth 76", title = "The Relation Between Computational and Denotational Properties for {Scott}'s {$D_\infty$}-Models of the Lambda-Calculus", journal = j-SIAM-J-COMPUT, volume = "5", number = "3", pages = "488--521", month = sep, year = "1976", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibsource = "Theory/CLiCS.bib, Misc/Functional.bib, Compiler/semantics.bib, Compiler/reynolds.bib, Compiler/prog.lang.theory.bib, Theory/CLiCS.bib", checked = "30 August 1989", keywords = "functional", } @Article{Csanky:1976:FPM, author = "L. Csanky", title = "Fast Parallel Matrix Inversion Algorithms", journal = j-SIAM-J-COMPUT, volume = "5", number = "4", pages = "618--623", month = dec, year = "1976", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibdate = "Thu Apr 9 08:04:33 1998", } @Article{Even:1976:CTM, author = "S. Even and A. Itai and A. Shamir", key = "Even et al.", title = "On the Complexity of Timetable and Multicommodity Flow Problems", journal = j-SIAM-J-COMPUT, volume = "5", number = "4", pages = "691--703", month = dec, year = "1976", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibdate = "Thu Jan 23 10:46:01 1997", bibsource = "Parallel/Multi.bib", } @Article{Cheriton:1976:FMS, author = "D. Cheriton and R. E. Tarjan", key = "Cheriton \& Tarjan", title = "Finding Minimum Spanning Trees", journal = j-SIAM-J-COMPUT, volume = "5", number = "4", pages = "724--742", month = dec, year = "1976", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibdate = "Thu Jan 23 10:46:11 1997", bibsource = "Parallel/Multi.bib, Graphics/siggraph/76.bib", oldlabel = "geom-1210", } @Article{Hecht:1977:SAG, author = "M. S. Hecht and J. D. Ullman", key = "Hecht \& Ullman", title = "A Simple Algorithm for Global Data Flow Analysis Problems", journal = j-SIAM-J-COMPUT, volume = "4", number = "4", pages = "519--532", month = dec, year = "1977", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibdate = "Thu Jul 23 17:31:02 1987", bibsource = "Compiler/compiler.bib", owner = "manning", xxnote = "Check volume/year: 4/1975 or 6/1977??", } @Article{Papadimitriou:1977:CLS, author = "Christos H. Papadimitriou and Kenneth Steiglitz", title = "The complexity of local search for the traveling salesman problem", journal = j-SIAM-J-COMPUT, volume = "6", number = "1", pages = "76--83", month = mar, year = "1977", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibdate = "Thu Jan 23 10:46:45 1997", bibsource = "Graphics/siggraph/77.bib", oldlabel = "geom-477.2", precedes = "p-etspn-77", succeeds = "ps-scrts-76", } @Article{Solovay:1977:FMC, author = "R. Solovay and Strassen V.", key = "Solovay \& Strassen", title = "A Fast {Monte-Carlo} Test for Primality", journal = j-SIAM-J-COMPUT, volume = "6", number = "1", pages = "84--85", month = mar, year = "1977", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibsource = "Parallel/Multi.bib", } @Article{Kafura:1977:TSM, author = "D. G. Kafura and V. Y. Shen", key = "Kafura \& Shen", title = "Task Scheduling on a Multiprocessor System with Independent Memories", journal = j-SIAM-J-COMPUT, volume = "6", number = "1", pages = "167--187", month = mar, year = "1977", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibsource = "Os/os.bib, Misc/os.bib", } @Article{Knuth:1977:FPM, author = "D. E. Knuth and J. H. Morris and V. R. Pratt", title = "Fast Pattern Matching in Strings", journal = j-SIAM-J-COMPUT, volume = "6", number = "2", pages = "323--350?", month = jun, year = "1977", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibdate = "Thu Jan 23 10:48:34 1997", bibsource = "Misc/traces.bib, Compiler/math.prog.construction.bib", annote = "", } @Article{Garey:1977:TPS, author = "M. R. Garey and D. S. Johnson", title = "Two-Processor Scheduling with Start-Times and Deadlines*", journal = j-SIAM-J-COMPUT, volume = "6", number = "3", pages = "416--428", month = sep, year = "1977", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibsource = "Database/Graefe.bib, Misc/Discrete.event.bib", } @Article{Lam:1977:WCA, author = "S. Lam and R. Sethi", title = "Worst Case Analysis of Two Scheduling Algorithms", journal = j-SIAM-J-COMPUT, volume = "6", number = "3", pages = "518", month = sep, year = "1977", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibsource = "Database/Graefe.bib", } @Article{Tarjan:1977:FMI, author = "Robert E. Tarjan and Anthony E. Trojanowski", title = "Finding a Maximum Independent Set", journal = j-SIAM-J-COMPUT, volume = "6", number = "3", pages = "537--546", month = "????", year = "1977", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibdate = "Thu Jan 23 10:47:18 1997", bibsource = "Theory/clique.color.bib", annote = "An implicit enumeration algorithm for maximum clique. Worst case running time is $O(2^{n/3})$.", } @Article{Rosenkrantz:1977:ASH, author = "Daniel J. Rosenkrantz and Richard E. Stearns and Philip M. {Lewis, II}", title = "An analysis of several heuristics for the traveling salesman problem", journal = j-SIAM-J-COMPUT, volume = "6", number = "3", pages = "563--581", month = "????", year = "1977", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibdate = "Thu Jan 23 10:48:23 1997", bibsource = "Graphics/siggraph/77.bib", oldlabel = "geom-516.2", succeeds = "rsl-aatsp-74", } @Article{Lee:1977:LPP, author = "D. T. Lee and F. P. Preparata", title = "Location of a Point in a Planar Subdivision and its Applications", journal = j-SIAM-J-COMPUT, volume = "6", number = "3", pages = "594--606", month = sep, year = "1977", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibsource = "Graphics/siggraph/77.bib, Database/Graefe.bib", oldlabel = "geom-349.2", succeeds = "lp-lppsa-76", } @Article{Cook:1978:SCA, author = "Stephen A. Cook", key = "Cook", title = "Soundness and Completeness of an Axiom System for Program Verification", journal = j-SIAM-J-COMPUT, volume = "7", number = "1", pages = "70--90", month = feb, year = "1978", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibdate = "Thu Jan 23 10:48:55 1997", bibsource = "Compiler/semantics.bib, Compiler/prog.lang.theory.bib", } @Article{Probert:1978:ECD, author = "Robert L. Probert", title = "An extension of computational duality to sequences of bilinear computations", journal = j-SIAM-J-COMPUT, volume = "7", number = "1", pages = "91--98", month = "????", year = "1978", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C05 (15A63 68B99)", MRnumber = "80j:68028", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Schnorr:1978:ATC, author = "C.-P. Schnorr", title = "An algorithm for transitive closure with linear expected time", journal = j-SIAM-J-COMPUT, volume = "7", number = "2", pages = "127--133", month = "????", year = "1978", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68E10 (68C05)", MRnumber = "80a:68073", MRreviewer = "Sukhamay Kundu", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Megiddo:1978:NAC, author = "Nimrod Megiddo and Arie Tamir", title = "An ${O}(n\cdot n)$ algorithm for a class of matching problems. {\rm log}", journal = j-SIAM-J-COMPUT, volume = "7", number = "2", pages = "154--157", month = "????", year = "1978", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C05 (68C25 68E10)", MRnumber = "80d:68042", MRreviewer = "Sukhamay Kundu", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Book:1978:LLI, author = "Ronald V. Book and Maurice Nivat", title = "Linear languages and the intersection closures of classes of languages", journal = j-SIAM-J-COMPUT, volume = "7", number = "2", pages = "167--177", month = "????", year = "1978", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68F05", MRnumber = "80a:68077", MRreviewer = "S. A. Greibach", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Frederickson:1978:AAS, author = "Greg N. Frederickson and Matthew S. Hecht and Chul E. Kim", title = "Approximation algorithms for some routing problems", journal = j-SIAM-J-COMPUT, volume = "7", number = "2", pages = "178--193", month = may, year = "1978", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", bibdate = "Thu Jan 23 10:49:28 1997", bibsource = "Graphics/siggraph/78.bib", oldlabel = "geom-2967.2", succeeds = "fhk-aasrp-76", } @Article{Arjomandi:1978:PCG, author = "Eshrat Reghbati Arjomandi and D. G. Corneil", title = "Parallel computations in graph theory", journal = j-SIAM-J-COMPUT, volume = "7", number = "2", pages = "230--237", month = "????", year = "1978", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (68B20 68E10)", MRnumber = "81b:68043", MRreviewer = "P. E. O'Neil", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Wadsworth:1978:ARL, author = "Christopher P. Wadsworth", title = "Approximate Reduction and Lambda Calculus Models", journal = j-SIAM-J-COMPUT, volume = "7", number = "3", pages = "337--356", month = aug, year = "1978", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "03B40 (68B10)", MRnumber = "81f:03020", bibdate = "Sat Jan 18 18:03:50 MST 1997", bibsource = "Theory/CLiCS.bib, Theory/CLiCS.bib, Compiler/reynolds.bib", acknowledgement = ack-nhfb, checked = "19 October 1990", } @Article{Bruno:1978:CTS, author = "John Bruno and Peter Downey", title = "Complexity of task sequencing with deadlines, setup times and changeover costs", journal = j-SIAM-J-COMPUT, volume = "7", number = "4", pages = "393--404", month = "????", year = "1978", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (90B35)", MRnumber = "80i:68029", MRreviewer = "L. E. Trotter, Jr.", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Rosenkrantz:1978:PAD, author = "Daniel J. Rosenkrantz and Harry B. {Hunt, III}", title = "Polynomial algorithms for deterministic pushdown automata", journal = j-SIAM-J-COMPUT, volume = "7", number = "4", pages = "405--412", month = "????", year = "1978", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (68D35)", MRnumber = "80f:68053", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Itai:1978:FMC, author = "Alon Itai and Michael Rodeh", title = "Finding a minimum circuit in a graph", journal = j-SIAM-J-COMPUT, volume = "7", number = "4", pages = "413--423", month = "????", year = "1978", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68E10 (68C25)", MRnumber = "80g:68088", MRreviewer = "L. E. Trotter, Jr.", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Ruskey:1978:GAT, author = "Frank Ruskey", title = "Generating $t$-ary trees lexicographically", journal = j-SIAM-J-COMPUT, volume = "7", number = "4", pages = "424--439", month = "????", year = "1978", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C05 (68E10)", MRnumber = "80f:68033", MRreviewer = "E. M. Reingold", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Selman:1978:PTE, author = "Alan L. Selman", title = "Polynomial time enumeration reducibility", journal = j-SIAM-J-COMPUT, volume = "7", number = "4", pages = "440--457", month = "????", year = "1978", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25", MRnumber = "80d:68059", MRreviewer = "John T. Gill", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Plaisted:1978:SPI, author = "David Plaisted", title = "Some polynomial and integer divisibility problems are ${NP}$-hard", journal = j-SIAM-J-COMPUT, volume = "7", number = "4", pages = "458--464", month = "????", year = "1978", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25", MRnumber = "80d:68055", MRreviewer = "Jan van Leeuwen", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Rosenberg:1978:MCT, author = "Arnold L. Rosenberg and Lawrence Snyder", title = "Minimal-comparison $2,\,3$-trees", journal = j-SIAM-J-COMPUT, volume = "7", number = "4", pages = "465--480", month = "????", year = "1978", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68H05 (68E10)", MRnumber = "80a:68115", MRreviewer = "Giorgio Ausiello", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Purdom:1978:TSP, author = "Paul W. Purdom", title = "Tree size by partial backtracking", journal = j-SIAM-J-COMPUT, volume = "7", number = "4", pages = "481--491", month = "????", year = "1978", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C05 (68E05)", MRnumber = "80f:68032", MRreviewer = "E. M. Reingold", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Trojanowski:1978:RLA, author = "Anthony E. Trojanowski", title = "Ranking and listing algorithms for $k$-ary trees", journal = j-SIAM-J-COMPUT, volume = "7", number = "4", pages = "492--509", month = "????", year = "1978", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68E10", MRnumber = "81k:68048", MRreviewer = "M. C. Golumbic", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Yao:1978:LSA, author = "Andrew Chi Chih Yao", title = "On the loop switching addressing problem", journal = j-SIAM-J-COMPUT, volume = "7", number = "4", pages = "515--523", month = "????", year = "1978", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68E10 (68B05)", MRnumber = "80c:68051", MRreviewer = "Fan R. K. Chung", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Ibarra:1978:UEP, author = "Oscar H. Ibarra", title = "The unsolvability of the equivalence problem for $\varepsilon $-free {NGSM}'s with unary input (output) alphabet and applications", journal = j-SIAM-J-COMPUT, volume = "7", number = "4", pages = "524--532", month = "????", year = "1978", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68D25 (68F05)", MRnumber = "80b:68070", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Baker:1978:TER, author = "Theodore P. Baker", title = "A technique for extending rapid exact-match string matching to arrays of more than one dimension", journal = j-SIAM-J-COMPUT, volume = "7", number = "4", pages = "533--541", month = "????", year = "1978", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68G10", MRnumber = "81h:68085", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{McDiarmid:1979:DCN, author = "Colin McDiarmid", title = "Determining the chromatic number of a graph", journal = j-SIAM-J-COMPUT, volume = "8", number = "1", pages = "1--14", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68E10 (05C15 68C25)", MRnumber = "84h:68050", MRreviewer = "D. Ya. Kesel'man", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Shiloach:1979:MLA, author = "Yossi Shiloach", title = "A minimum linear arrangement algorithm for undirected trees", journal = j-SIAM-J-COMPUT, volume = "8", number = "1", pages = "15--32", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (68E10)", MRnumber = "80c:68034", MRreviewer = "Henry S. Warren, Jr.", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Brown:1979:PAR, author = "Mark R. Brown", title = "A partial analysis of random height-balanced trees", journal = j-SIAM-J-COMPUT, volume = "8", number = "1", pages = "33--41", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68B10 (68E05)", MRnumber = "80b:68017", MRreviewer = "Stephen Soule", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Miller:1979:OT, author = "Raymond E. Miller and Nicholas Pippenger and Arnold L. Rosenberg and Lawrence Snyder", title = "Optimal $2,\,3$-trees", journal = j-SIAM-J-COMPUT, volume = "8", number = "1", pages = "42--59", month = feb, year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68E10 (68B10)", MRnumber = "80c:68050", MRreviewer = "Richard A. DeMillo", bibdate = "Thu Jan 23 10:51:10 1997", bibsource = "Database/Wiederhold.bib", note = "Also published in/as: IBM, TJWRC, Res.R. RC 6505, 1977.", acknowledgement = ack-nhfb, } @Article{Aggarwal:1979:REM, author = "Vijay B. Aggarwal and James W. Burgmeier", title = "A round-off error model with applications to arithmetic expressions", journal = j-SIAM-J-COMPUT, volume = "8", number = "1", pages = "60--72", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C01 (65G05)", MRnumber = "81b:68031", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Zaks:1979:GTO, author = "S. Zaks and D. Richards", title = "Generating trees and other combinatorial objects lexicographically", journal = j-SIAM-J-COMPUT, volume = "8", number = "1", pages = "73--81", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68E10 (05C05)", MRnumber = "80f:68078", MRreviewer = "Fabrizio Luccio", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Bitner:1979:HDO, author = "James R. Bitner", title = "Heuristics that dynamically organize data structures", journal = j-SIAM-J-COMPUT, volume = "8", number = "1", pages = "82--110", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68B15 (68E05 68H05)", MRnumber = "80i:68010", MRreviewer = "Hans-Peter Kriegel", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Opatrny:1979:TOP, author = "J. Opatrn{\'y}", title = "Total ordering problem", journal = j-SIAM-J-COMPUT, volume = "8", number = "1", pages = "111--114", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25", MRnumber = "80e:68117", MRreviewer = "Ondrej S\'ykora", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Harper:1979:LBS, author = "L. H. Harper and J. E. Savage", title = "Lower bounds on synchronous combinational complexity", journal = j-SIAM-J-COMPUT, volume = "8", number = "2", pages = "115--119", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25", MRnumber = "80c:68027", MRreviewer = "Y. L. Varol", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Hyafil:1979:PEM, author = "Laurent Hyafil", title = "On the parallel evaluation of multivariate polynomials", journal = j-SIAM-J-COMPUT, volume = "8", number = "2", pages = "120--123", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25", MRnumber = "80c:68031", MRreviewer = "Y. L. Varol", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Hehner:1979:NRR, author = "E. C. R. Hehner and R. N. S. Horspool", title = "A new representation of the rational numbers for fast easy arithmetic", journal = j-SIAM-J-COMPUT, volume = "8", number = "2", pages = "124--134", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C05 (10A30 68A05)", MRnumber = "80h:68027", MRreviewer = "P. J. Weinberger", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Itai:1979:MFP, author = "Alon Itai and Yossi Shiloach", title = "Maximum flow in planar networks", journal = j-SIAM-J-COMPUT, volume = "8", number = "2", pages = "135--150", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "90B10 (68C25)", MRnumber = "80i:90052", MRreviewer = "Takao Ozawa", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Stockmeyer:1979:PDC, author = "Larry J. Stockmeyer and Ashok K. Chandra", title = "Provably difficult combinatorial games", journal = j-SIAM-J-COMPUT, volume = "8", number = "2", pages = "151--174", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (90Dxx)", MRnumber = "80d:68060", MRreviewer = "Y. L. Varol", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Mehlhorn:1979:DBS, author = "Kurt Mehlhorn", title = "Dynamic binary search", journal = j-SIAM-J-COMPUT, volume = "8", number = "2", pages = "175--198", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68H05 (68C25)", MRnumber = "80h:68081", MRreviewer = "Eberhard L{\"u}dde", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Carlson:1979:CRP, author = "Carl R. Carlson", title = "A counterexample to {Reingold}'s pushdown permuter characterization theorem", journal = j-SIAM-J-COMPUT, volume = "8", number = "2", pages = "199--201", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C05", MRnumber = "80h:68025", MRreviewer = "R. K. Shyamasundar", bibdate = "Fri Oct 27 15:21:46 2000", acknowledgement = ack-nhfb, } @Article{Coffman:1979:CAE, author = "E. G. {Coffman, Jr.} and Joseph Y.-T. Leung", title = "Combinatorial analysis of an efficient algorithm for processor and storage allocation", journal = j-SIAM-J-COMPUT, volume = "8", number = "2", pages = "202--217", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25", MRnumber = "81c:68027", MRreviewer = "Donald B. Johnson", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Aho:1979:EAR, author = "A. V. Aho and Y. Sagiv and J. D. Ullman", title = "Equivalences among relational expressions", journal = j-SIAM-J-COMPUT, volume = "8", number = "2", pages = "218--246", month = may, year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68H05 (68B15)", MRnumber = "80f:68108", MRreviewer = "Yu. G. Karpov", bibdate = "Thu Jan 23 10:51:32 1997", bibsource = "Database/Graefe.bib", acknowledgement = ack-nhfb, keywords = "tableaux optimization", } @Article{Hagihara:1979:DPM, author = "Kenichi Hagihara and Minoru Ito and Kenichi Taniguchi and Tadao Kasami", title = "Decision problems for multi-valued dependencies in relational databases.", journal = j-SIAM-J-COMPUT, volume = "8", number = "2", pages = "247--264", month = may, year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C05 (68B15)", MRnumber = "80c:68021", bibdate = "Sat Jan 18 18:03:50 MST 1997", bibsource = "Distributed/gesturing.bib", acknowledgement = ack-nhfb, } @Article{Schnorr:1979:BEC, author = "C.-P. Schnorr", title = "Bottlenecks and edge connectivity in unsymmetrical networks", journal = j-SIAM-J-COMPUT, volume = "8", number = "2", pages = "265--274", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "90B10 (68C25)", MRnumber = "80g:90045", MRreviewer = "Tadashi Nakamura", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Sahni:1979:NLS, author = "Sartaj Sahni and Yookun Cho", title = "Nearly on line scheduling of a uniform processor system with release times", journal = j-SIAM-J-COMPUT, volume = "8", number = "2", pages = "275--285", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C15 (90B35)", MRnumber = "80d:68046", MRreviewer = "Eugene Levner", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Stoutemyer:1979:AAB, author = "David R. Stoutemyer", title = "Automatic asymptotic and big-${O}$ calculations via computer algebra", journal = j-SIAM-J-COMPUT, volume = "8", number = "3", pages = "287--299", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25", MRnumber = "80e:68123", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Wang:1979:NAP, author = "Paul S. Wang and Barry M. Trager", title = "New algorithms for polynomial squarefree decomposition over the integers", journal = j-SIAM-J-COMPUT, volume = "8", number = "3", pages = "300--305", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C20 (68C05)", MRnumber = "80e:68093", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Wirth:1979:SVD, author = "Michael C. Wirth", title = "Symbolic vector and dyadic analysis", journal = j-SIAM-J-COMPUT, volume = "8", number = "3", pages = "306--319", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C20 (76A99)", MRnumber = "80e:68094", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Epstein:1979:NST, author = "H. I. Epstein", title = "A natural structure theorem for complex fields", journal = j-SIAM-J-COMPUT, volume = "8", number = "3", pages = "320--325", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "12H05 (10F35 12L99 68C20)", MRnumber = "82i:12025", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Klip:1979:NAP, author = "Dorothea A. Klip", title = "New algorithms for polynomial multiplication", journal = j-SIAM-J-COMPUT, volume = "8", number = "3", pages = "326--343", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C05 (68C25 68E05)", MRnumber = "80h:68029", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{McKay:1979:SRC, author = "J. McKay", title = "Some remarks on computing {Galois} groups", journal = j-SIAM-J-COMPUT, volume = "8", number = "3", pages = "344--347", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "12A55 (20B25)", MRnumber = "80m:12005", MRreviewer = "Harvey Cohn", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Yun:1979:UBC, author = "David Y. Y. Yun", title = "Uniform bounds for a class of algebraic mappings", journal = j-SIAM-J-COMPUT, volume = "8", number = "3", pages = "348--356", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (94A12)", MRnumber = "80e:68129", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Rothstein:1979:STE, author = "Michael Rothstein and B. F. Caviness", title = "A structure theorem for exponential and primitive functions", journal = j-SIAM-J-COMPUT, volume = "8", number = "3", pages = "357--367", month = aug, year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "12H05 (68C20)", MRnumber = "80m:12028", MRreviewer = "Michael F. Singer", bibdate = "Sat Jan 18 18:03:50 MST 1997", bibsource = "Theory/Comp.Alg.1.bib", acknowledgement = ack-nhfb, } @Article{Yao:1979:CPM, author = "Andrew Chi Chih Yao", title = "The complexity of pattern matching for a random string", journal = j-SIAM-J-COMPUT, volume = "8", number = "3", pages = "368--387", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25", MRnumber = "80g:68064", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Stockmeyer:1979:NCF, author = "L. J. Stockmeyer and C. K. Wong", title = "On the number of comparisons to find the intersection of two relations", journal = j-SIAM-J-COMPUT, volume = "8", number = "3", pages = "388--404", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (68E05)", MRnumber = "80e:68122", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Papadimitriou:1979:SIO, author = "C. H. Papadimitriou and M. Yannakakis", title = "Scheduling interval-ordered tasks", journal = j-SIAM-J-COMPUT, volume = "8", number = "3", pages = "405--409", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C15 (68C25)", MRnumber = "80e:68087", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Valiant:1979:CER, author = "Leslie G. Valiant", title = "The Complexity of Enumeration and Reliability Problems", journal = j-SIAM-J-COMPUT, volume = "8", number = "3", pages = "410--421", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25", MRnumber = "80f:68055", bibdate = "Sat Jan 18 18:03:50 MST 1997", bibsource = "Ai/nonmono.bib", acknowledgement = ack-nhfb, } @Article{Shiloach:1979:MF, author = "Yossi Shiloach", title = "Multiterminal $0-1$ flow", journal = j-SIAM-J-COMPUT, volume = "8", number = "3", pages = "422--430", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "90B10 (68C25 68E10)", MRnumber = "81c:90043", MRreviewer = "Andr{\'a}s Frank", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Fortune:1979:NSC, author = "Steven Fortune", title = "A note on sparse complete sets", journal = j-SIAM-J-COMPUT, volume = "8", number = "3", pages = "431--433", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25", MRnumber = "80f:68045", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Book:1979:PST, author = "Ronald V. Book", title = "Polynomial space and transitive closure", journal = j-SIAM-J-COMPUT, volume = "8", number = "3", pages = "434--439", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25", MRnumber = "80e:68098", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Walkup:1979:EVR, author = "David W. Walkup", title = "On the expected value of a random assignment problem", journal = j-SIAM-J-COMPUT, volume = "8", number = "3", pages = "440--442", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68E99 (05C99)", MRnumber = "80e:68176", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{JaJa:1979:OEP, author = "Joseph Ja'Ja'", title = "Optimal evaluation of pairs of bilinear forms", journal = j-SIAM-J-COMPUT, volume = "8", number = "3", pages = "443--462", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25", MRnumber = "80e:68109", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Gonnet:1979:EOH, author = "Gaston H. Gonnet and J. Ian Munro", title = "Efficient ordering of hash tables", journal = j-SIAM-J-COMPUT, volume = "8", number = "3", pages = "463--478", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68H05", MRnumber = "80e:68237", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Bitner:1979:ONO, author = "J. R. Bitner and C. K. Wong", title = "Optimal and near-optimal scheduling algorithms for batched processing in linear storage", journal = j-SIAM-J-COMPUT, volume = "8", number = "4", pages = "479--498", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C15", MRnumber = "81i:68046", MRreviewer = "Jacek B{\l}a\.zewicz", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Kannan:1979:PAC, author = "Ravindran Kannan and Achim Bachem", title = "Polynomial algorithms for computing the {Smith} and {Hermite} normal forms of an integer matrix", journal = j-SIAM-J-COMPUT, volume = "8", number = "4", pages = "499--507", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "15-04 (15A21 68C25)", MRnumber = "81k:15002", MRreviewer = "Robert M. McConnel", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Priese:1979:TPC, author = "Lutz Priese", title = "Towards a precise characterization of the complexity of universal and nonuniversal {Turing} machines", journal = j-SIAM-J-COMPUT, volume = "8", number = "4", pages = "508--523", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "03D15 (03D10 68C25 68C40)", MRnumber = "81k:03035", MRreviewer = "Cristian Calude", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Bagchi:1979:OT, author = "A. Bagchi and J. K. Roy", title = "On ${V}$-optimal trees", journal = j-SIAM-J-COMPUT, volume = "8", number = "4", pages = "524--541", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68E05 (05C05 90B99)", MRnumber = "83b:68071", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Preparata:1979:NLS, author = "F. P. Preparata", title = "A note on locating a set of points in a planar subdivision", journal = j-SIAM-J-COMPUT, volume = "8", number = "4", pages = "542--545", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25", MRnumber = "81f:68056", MRreviewer = "D. T. Lee", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Donahue:1979:ST, author = "James Donahue", title = "On the semantics of {``data type''}", journal = j-SIAM-J-COMPUT, volume = "8", number = "4", pages = "546--560", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68B10 (03B40 68B15)", MRnumber = "82f:68015", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Karp:1979:PAN, author = "Richard M. Karp", title = "A patching algorithm for the nonsymmetric traveling-salesman problem", journal = j-SIAM-J-COMPUT, volume = "8", number = "4", pages = "561--573", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "90C08 (68C25)", MRnumber = "82c:90057", MRreviewer = "B. Korte", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Kasai:1979:CPG, author = "Takumi Kasai and Akeo Adachi and Shigeki Iwata", title = "Classes of pebble games and complete problems", journal = j-SIAM-J-COMPUT, volume = "8", number = "4", pages = "574--586", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (90D05)", MRnumber = "82a:68075", MRreviewer = "Aviezri S. Fraenkel", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Weyuker:1979:TDQ, author = "Elaine J. Weyuker", title = "Translatability and decidability questions for restricted classes of program schemas", journal = j-SIAM-J-COMPUT, volume = "8", number = "4", pages = "587--598", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68B10", MRnumber = "81i:68028", MRreviewer = "M. B. Trakhtenbrot", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Maier:1979:EMS, author = "David Maier", title = "An Efficient Method for Storing Ancestor Information in Trees", journal = j-SIAM-J-COMPUT, volume = "8", number = "4", pages = "599--618", month = nov, year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (92A20)", MRnumber = "81k:68034", MRreviewer = "Fabrizio Luccio", bibdate = "Sat Jan 18 18:03:50 MST 1997", bibsource = "Database/Wiederhold.bib", acknowledgement = ack-nhfb, } @Article{Krishnamoorthy:1979:NDN, author = "M. S. Krishnamoorthy and Narsingh Deo", title = "Node-deletion {NP}-complete problems", journal = j-SIAM-J-COMPUT, volume = "8", number = "4", pages = "619--625", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (05C35 68E10)", MRnumber = "83b:68037", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Probst:1979:FAP, author = "David K. Probst and Vangalur S. Alagar", title = "A family of algorithms for powering sparse polynomials", journal = j-SIAM-J-COMPUT, volume = "8", number = "4", pages = "626--644", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25", MRnumber = "81f:68057a", MRreviewer = "Daniel Lazard", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Shamir:1979:LTA, author = "Adi Shamir", title = "A linear time algorithm for finding minimum cutsets in reducible graphs", journal = j-SIAM-J-COMPUT, volume = "8", number = "4", pages = "645--655", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68E10 (68C05 68C25)", MRnumber = "81f:68077", MRreviewer = "Kabekode V. S. Bhat", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Hikita:1979:CCC, author = "T. Hikita and A. Nozaki", title = "Corrigenda: {{``A completeness criterion for spectra''} [SIAM J. Comput. {\bf 6} (1977), no. 2, 285--297, MR {\bf 57} \#2759].}", journal = j-SIAM-J-COMPUT, volume = "8", number = "4", pages = "656--656", month = "????", year = "1979", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "94C99", MRnumber = "81d:94053", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Tucker:1980:ETC, author = "Alan Tucker", title = "An efficient test for circular-arc graphs", journal = j-SIAM-J-COMPUT, volume = "9", number = "1", pages = "1--24", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68E10 (05C99)", MRnumber = "81a:68074", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Bloom:1980:SIE, author = "Stephen L. Bloom and Calvin C. Elgot and Jesse B. Wright", title = "Solutions of the iteration equation and extensions of the scalar iteration operation", journal = j-SIAM-J-COMPUT, volume = "9", number = "1", pages = "25--45", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68B05", MRnumber = "81i:68021a", MRreviewer = "J. D. Rutledge", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Kintala:1980:RNR, author = "Chandra M. R. Kintala and Patrick C. Fischer", title = "Refining nondeterminism in relativized polynomial-time bounded computations", journal = j-SIAM-J-COMPUT, volume = "9", number = "1", pages = "46--53", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (68F10)", MRnumber = "81b:68049", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Brent:1980:CCG, author = "Richard P. Brent and Joseph F. Traub", title = "On the Complexity of Composition and Generalized Composition of Power Series", journal = j-SIAM-J-COMPUT, volume = "9", number = "1", pages = "54--66", month = feb, year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C20", MRnumber = "81b:68042", bibdate = "Sat Jan 18 18:03:50 MST 1997", bibsource = "Theory/auto.diff.bib", acknowledgement = ack-nhfb, } @Article{Hennessy:1980:SCV, author = "M. C. B. Hennessy", title = "The semantics of call-by-value and call-by-name in a nondeterministic environment", journal = j-SIAM-J-COMPUT, volume = "9", number = "1", pages = "67--84", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68F20", MRnumber = "82b:68072", MRreviewer = "A. V. An\=\i s\=\i mov", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Stockmeyer:1980:OLM, author = "Paul K. Stockmeyer and F. Frances Yao", title = "On the optimality of linear merge", journal = j-SIAM-J-COMPUT, volume = "9", number = "1", pages = "85--90", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25", MRnumber = "81b:68057", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Cho:1980:BLS, author = "Yookun Cho and Sartaj Sahni", title = "Bounds for list schedules on uniform processors", journal = j-SIAM-J-COMPUT, volume = "9", number = "1", pages = "91--103", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C15", MRnumber = "81a:68041", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Statman:1980:WCE, author = "R. Statman", title = "Worst case exponential lower bounds for input resolution with paramodulation", journal = j-SIAM-J-COMPUT, volume = "9", number = "1", pages = "104--110", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68G15 (68C25)", MRnumber = "81e:68115", MRreviewer = "G. E. Peterson", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Wong:1980:EMW, author = "C. K. Wong and M. C. Easton", title = "An efficient method for weighted sampling without replacement", journal = j-SIAM-J-COMPUT, volume = "9", number = "1", pages = "111--113", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (62D05)", MRnumber = "81a:68054", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Hartmanis:1980:SDR, author = "J. Hartmanis", title = "On the succinctness of different representations of languages", journal = j-SIAM-J-COMPUT, volume = "9", number = "1", pages = "114--120", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68F05", MRnumber = "81a:68082", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Dobkin:1980:ACM, author = "David Dobkin and Richard J. Lipton", title = "Addition chain methods for the evaluation of specific polynomials", journal = j-SIAM-J-COMPUT, volume = "9", number = "1", pages = "121--125", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25", MRnumber = "81a:68046", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Hirschberg:1980:CSS, author = "D. S. Hirschberg", title = "On the complexity of searching a set of vectors", journal = j-SIAM-J-COMPUT, volume = "9", number = "1", pages = "126--129", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25", MRnumber = "81a:68048", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Joichi:1980:CGC, author = "J. T. Joichi and Dennis E. White and S. G. Williamson", title = "Combinatorial {Gray} codes", journal = j-SIAM-J-COMPUT, volume = "9", number = "1", pages = "130--141", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C05 (94B25)", MRnumber = "81g:68050", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Flajolet:1980:NGC, author = "P. Flajolet and Lyle Ramshaw", title = "A note on {Gray} code and odd-even merge", journal = j-SIAM-J-COMPUT, volume = "9", number = "1", pages = "142--158", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (68E05)", MRnumber = "81h:68025", MRreviewer = "Jean Vuillemin", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Rosen:1980:MRD, author = "Barry K. Rosen", title = "Monoids for rapid data flow analysis", journal = j-SIAM-J-COMPUT, volume = "9", number = "1", pages = "159--196", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68B05", MRnumber = "81h:68007", MRreviewer = "Fabrizio Luccio", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Galil:1980:FVC, author = "Zvi Galil", title = "Finding the vertex connectivity of graphs", journal = j-SIAM-J-COMPUT, volume = "9", number = "1", pages = "197--199", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68E10", MRnumber = "81d:68081", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Lee:1980:VDM, author = "D. T. Lee and C. K. Wong", title = "{Vorono{\u{\i}}} diagrams in {$L_{1}$} ({$L_{\infty}$}) metrics with {$2$}-dimensional storage applications", journal = j-SIAM-J-COMPUT, volume = "9", number = "1", pages = "200--211", month = feb, year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C15 (68H05)", MRnumber = "81d:68053", bibdate = "Thu Jan 23 10:51:48 1997", bibsource = "Graphics/siggraph/80.bib", acknowledgement = ack-nhfb, oldlabel = "geom-357", } @Article{Babai:1980:CCL, author = "L{\'a}szl{\'o} Babai", title = "On the complexity of canonical labeling of strongly regular graphs", journal = j-SIAM-J-COMPUT, volume = "9", number = "1", pages = "212--216", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (68E10)", MRnumber = "81d:68055", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Hehner:1980:CNR, author = "E. C. R. Hehner and R. N. S. Horspool", title = "Corrigendum: {{``A new representation of the rational numbers for fast easy arithmetic''} [SIAM J. Comput. {\bf 8} (1979), no. 2, 124--134, MR 80h:68027]}", journal = j-SIAM-J-COMPUT, volume = "9", number = "1", pages = "217--217", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C05 (10A30)", MRnumber = "81f:68044", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Shiloach:1980:MMC, author = "Yossi Shiloach", title = "A multiterminal minimum cut algorithm for planar graphs", journal = j-SIAM-J-COMPUT, volume = "9", number = "2", pages = "219--224", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (05C10 05C35 68E10)", MRnumber = "82c:68027", MRreviewer = "E. Rodney Canfield", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Winograd:1980:MPM, author = "S. Winograd", title = "On multiplication of polynomials modulo a polynomial", journal = j-SIAM-J-COMPUT, volume = "9", number = "2", pages = "225--229", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "12-04 (12A20 68C25)", MRnumber = "82j:12001", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Pippenger:1980:EPM, author = "Nicholas Pippenger", title = "On the evaluation of powers and monomials", journal = j-SIAM-J-COMPUT, volume = "9", number = "2", pages = "230--250", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "10L05 (10M99 68C25)", MRnumber = "82c:10064", MRreviewer = "D. G. Cantor", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Morgera:1980:ESI, author = "Salvatore D. Morgera", title = "Efficient synthesis and implementation of large discrete {Fourier} transformations", journal = j-SIAM-J-COMPUT, volume = "9", number = "2", pages = "251--272", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "94A11 (65T05)", MRnumber = "81e:94002", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Rabin:1980:PAF, author = "Michael O. Rabin", title = "Probabilistic algorithms in finite fields", journal = j-SIAM-J-COMPUT, volume = "9", number = "2", pages = "273--280", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "12-04 (12C05 68C25)", MRnumber = "81g:12002", MRreviewer = "Duncan A. Buell", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Corneil:1980:TAV, author = "D. G. Corneil and D. G. Kirkpatrick", title = "A theoretical analysis of various heuristics for the graph isomorphism problem", journal = j-SIAM-J-COMPUT, volume = "9", number = "2", pages = "281--297", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "05C99 (68C25)", MRnumber = "81j:05091", MRreviewer = "V. B. Alekseev", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Hwang:1980:OME, author = "F. K. Hwang", title = "Optimal merging of $3$ elements with $n$ elements", journal = j-SIAM-J-COMPUT, volume = "9", number = "2", pages = "298--320", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (68E05)", MRnumber = "82c:68022", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Pan:1980:NFA, author = "V. Ya. Pan", title = "New fast algorithms for matrix operations", journal = j-SIAM-J-COMPUT, volume = "9", number = "2", pages = "321--342", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "65F30 (68C25)", MRnumber = "81f:65037", MRreviewer = "Francesco Romani", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Yao:1980:PDP, author = "Andrew C. Yao and Ronald L. Rivest", title = "On the polyhedral decision problem", journal = j-SIAM-J-COMPUT, volume = "9", number = "2", pages = "343--347", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (52A25 90C25)", MRnumber = "82h:68071", MRreviewer = "Jaroslav Mor{\'a}vek", bibdate = "Sat Jan 18 18:03:50 MST 1997", bibsource = "Graphics/siggraph/80.bib", acknowledgement = ack-nhfb, oldlabel = "geom-659.2", succeeds = "yar-olbsp-77", } @Article{Gurari:1980:PSC, author = "Eitan M. Gurari and Oscar H. Ibarra", title = "Path systems: constructions, solutions and applications", journal = j-SIAM-J-COMPUT, volume = "9", number = "2", pages = "348--374", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (03D15 68C40)", MRnumber = "82f:68048", MRreviewer = "W. Bucher", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Reif:1980:CM, author = "John H. Reif", title = "Code motion", journal = j-SIAM-J-COMPUT, volume = "9", number = "2", pages = "375--395", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68B10", MRnumber = "81j:68024", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Hunt:1980:CCP, author = "H. B. {Hunt, III} and R. L. Constable and S. Sahni", title = "On the computational complexity of program scheme equivalence", journal = j-SIAM-J-COMPUT, volume = "9", number = "2", pages = "396--416", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (03D15 68B10)", MRnumber = "81j:68051", MRreviewer = "Steven S. Muchnick", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Galil:1980:SSF, author = "Zvi Galil and Joel Seiferas", title = "Saving space in fast string-matching", journal = j-SIAM-J-COMPUT, volume = "9", number = "2", pages = "417--438", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C20 (68C25)", MRnumber = "81i:68052", MRreviewer = "Stanley H. Benton, Jr.", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Probst:1980:CFA, author = "David K. Probst and Vangalur S. Alagar", title = "Corrigendum: {``A family of algorithms for powering sparse polynomials''}", journal = j-SIAM-J-COMPUT, volume = "9", number = "2", pages = "439--439", month = may, year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "439.68C25", MRnumber = "81f:68057b", MRreviewer = "Daniel Lazard", bibdate = "Thu Jan 23 10:52:08 1997", acknowledgement = ack-nhfb, } @Article{Ehrig:1980:MRH, author = "Hartmut Ehrig and Barry K. Rosen", title = "The mathematics of record handling", journal = j-SIAM-J-COMPUT, volume = "9", number = "3", pages = "441--469", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68B15 (68E10)", MRnumber = "81j:68031", MRreviewer = "W. W. Armstrong", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Parker:1980:COH, author = "D. Stott {Parker, Jr.}", title = "Conditions for optimality of the {Huffman} algorithm", journal = j-SIAM-J-COMPUT, volume = "9", number = "3", pages = "470--489", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68E05 (68C05 90C50)", MRnumber = "82e:68064", MRreviewer = "M. C. Golumbic", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Schonhage:1980:SMM, author = "A. Sch{\"o}nhage", title = "Storage modification machines", journal = j-SIAM-J-COMPUT, volume = "9", number = "3", pages = "490--508", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C40 (03D15)", MRnumber = "82b:68040", MRreviewer = "Robert M. Baer", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Rytter:1980:CPA, author = "Wojciech Rytter", title = "A correct preprocessing algorithm for {Boyer--Moore} string-searching", journal = j-SIAM-J-COMPUT, volume = "9", number = "3", pages = "509--512", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68H05 (68C05)", MRnumber = "81g:68129", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Gilbert:1980:PPI, author = "John R. Gilbert and Thomas Lengauer and Robert Endre Tarjan", title = "The pebbling problem is complete in polynomial space", journal = j-SIAM-J-COMPUT, volume = "9", number = "3", pages = "513--524", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (90D05)", MRnumber = "83c:68044", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Bloom:1980:VIP, author = "Stephen L. Bloom and Calvin C. Elgot and Jesse B. Wright", title = "Vector iteration in pointed iterative theories", journal = j-SIAM-J-COMPUT, volume = "9", number = "3", pages = "525--540", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68B05", MRnumber = "81i:68021b", MRreviewer = "J. D. Rutledge", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Jaffe:1980:BST, author = "Jeffrey M. Jaffe", title = "Bounds on the scheduling of typed task systems", journal = j-SIAM-J-COMPUT, volume = "9", number = "3", pages = "541--551", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C15 (90B35)", MRnumber = "82a:68061", MRreviewer = "Amnon Barak", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Weide:1980:RGG, author = "Bruce W. Weide", title = "Random graphs and graph optimization problems", journal = j-SIAM-J-COMPUT, volume = "9", number = "3", pages = "552--557", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68E10 (05C99 68C25 90C35)", MRnumber = "83c:68085", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Lawler:1980:GAM, author = "E. L. Lawler and J. K. Lenstra and A. H. G. Rinnooy Kan", title = "Generating all maximal independent sets: {NP}-hardness and polynomial-time algorithms", journal = j-SIAM-J-COMPUT, volume = "9", number = "3", pages = "558--565", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C05 (68C25)", MRnumber = "81j:68044", MRreviewer = "O. D'Antona", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Yao:1980:BSN, author = "Andrew Chi Chih Yao", title = "Bounds on selection networks", journal = j-SIAM-J-COMPUT, volume = "9", number = "3", pages = "566--582", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68E10 (68C25)", MRnumber = "83c:68087", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{George:1980:OAS, author = "Alan George and Joseph W. H. Liu", title = "An optimal algorithm for symbolic factorization of symmetric matrices", journal = j-SIAM-J-COMPUT, volume = "9", number = "3", pages = "583--593", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (15A23 65F30)", MRnumber = "83c:68043", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Brown:1980:DAD, author = "Mark R. Brown and Robert E. Tarjan", title = "Design and analysis of a data structure for representing sorted lists", journal = j-SIAM-J-COMPUT, volume = "9", number = "3", pages = "594--614", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68H05 (68C25 68E05)", MRnumber = "82e:68101", MRreviewer = "Eberhard L{\"u}dde", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Lipton:1980:APS, author = "Richard J. Lipton and Robert Endre Tarjan", title = "Applications of a Planar Separator Theorem", journal = j-SIAM-J-COMPUT, volume = "9", number = "3", pages = "615--627", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68E10 (05C10 05C70 68C25)", MRnumber = "82e:68067", MRreviewer = "Eberhard L{\"u}dde", bibdate = "Sat Jan 18 18:03:50 MST 1997", bibsource = "Theory/partition.bib, Graphics/siggraph/80.bib", acknowledgement = ack-nhfb, oldlabel = "geom-382.2", succeeds = "lt-apst-77", } @Article{Babai:1980:RGI, author = "L{\'a}szl{\'o} Babai and Paul Erd{\H{o}}s and Stanley M. Selkow", title = "Random graph isomorphism", journal = j-SIAM-J-COMPUT, volume = "9", number = "3", pages = "628--635", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68E10 (05C99)", MRnumber = "83c:68071", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Cook:1980:SLB, author = "Stephen A. Cook and Charles W. Rackoff", title = "Space lower bounds for maze threadability on restricted machines", journal = j-SIAM-J-COMPUT, volume = "9", number = "3", pages = "636--652", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (68D99)", MRnumber = "81k:68028", MRreviewer = "L{\'a}szl{\'o} Lov{\'a}sz", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Tai:1980:PCF, author = "Kuo Chung Tai", title = "Predictors of context-free grammars", journal = j-SIAM-J-COMPUT, volume = "9", number = "3", pages = "653--664", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68F25", MRnumber = "81k:68066", MRreviewer = "Michael Bauer", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Apt:1980:CFS, author = "Krzysztof R. Apt and Lambert G. L. T. Meertens", title = "Completeness with finite systems of intermediate assertions for recursive program schemes", journal = j-SIAM-J-COMPUT, volume = "9", number = "4", pages = "665--671", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68B10", MRnumber = "82j:68004", MRreviewer = "Stephen L. Bloom", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Guibas:1980:NPL, author = "Leo J. Guibas and Andrew M. Odlyzko", title = "A new proof of the linearity of the {Boyer--Moore} string searching algorithm", journal = j-SIAM-J-COMPUT, volume = "9", number = "4", pages = "672--682", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C05 (68C25 68E99)", MRnumber = "82d:68024", MRreviewer = "Armin Cremers", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Bloom:1980:COM, author = "Stephen L. Bloom and Ralph Tindell", title = "Compatible orderings on the metric theory of trees", journal = j-SIAM-J-COMPUT, volume = "9", number = "4", pages = "683--691", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68E10 (05C05 06A10)", MRnumber = "82f:68063", MRreviewer = "M. C. Golumbic", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Bini:1980:ASB, author = "Dario Bini and Grazia Lotti and Francesco Romani", title = "Approximate solutions for the bilinear form computational problem", journal = j-SIAM-J-COMPUT, volume = "9", number = "4", pages = "692--697", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (65F30)", MRnumber = "82a:68065", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Plaisted:1980:AMP, author = "David A. Plaisted", title = "The application of multivariate polynomials to inference rules and partial tests for unsatisfiability", journal = j-SIAM-J-COMPUT, volume = "9", number = "4", pages = "698--705", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (03B35)", MRnumber = "82g:68045", MRreviewer = "P. {\v{S}}t{\v{e}}p{\'a}nek", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Beyer:1980:CTG, author = "Terry Beyer and Sandra Mitchell Hedetniemi", title = "Constant time generation of rooted trees", journal = j-SIAM-J-COMPUT, volume = "9", number = "4", pages = "706--712", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68E10", MRnumber = "82b:68054", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{JaJa:1980:CBF, author = "Joseph Ja'Ja'", title = "On the complexity of bilinear forms with commutativity", journal = j-SIAM-J-COMPUT, volume = "9", number = "4", pages = "713--728", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (03D15 10C05 15A63)", MRnumber = "82f:68049", MRreviewer = "S. Hitotumatu", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Book:1980:ESC, author = "Ronald V. Book and Franz-Josef Brandenburg", title = "Equality sets and complexity classes", journal = j-SIAM-J-COMPUT, volume = "9", number = "4", pages = "729--743", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C40 (03D15 68C25 68F05)", MRnumber = "82h:68074", MRreviewer = "Karel {\v{C}}ul{\'\i}k", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Nassimi:1980:FCC, author = "David Nassimi and Sartaj Sahni", key = "Nassimi \& Sahni", title = "Finding connected components and connected ones on a mesh-connected parallel computer", journal = j-SIAM-J-COMPUT, volume = "9", number = "4", pages = "744--757", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68E10 (68A05 68B20 68C05)", MRnumber = "82e:68069", MRreviewer = "Danny Dolev", bibdate = "Sat Jan 18 18:03:50 MST 1997", bibsource = "Parallel/Multi.bib", acknowledgement = ack-nhfb, } @Article{Seroussi:1980:FSM, author = "Gadiel Seroussi and Abraham Lempel", title = "Factorization of symmetric matrices and trace-orthogonal bases in finite fields", journal = j-SIAM-J-COMPUT, volume = "9", number = "4", pages = "758--767", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "15A23 (15A33)", MRnumber = "81k:15019", MRreviewer = "Bradley W. Dickinson", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Feldman:1980:MPT, author = "Jerome A. Feldman and Anil Nigam", title = "A model and proof technique for message-based systems", journal = j-SIAM-J-COMPUT, volume = "9", number = "4", pages = "768--784", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68B10 (68J10)", MRnumber = "82a:68020", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Majster:1980:ELC, author = "Mila E. Majster and Angelika Reiser", title = "Efficient on-line construction and correction of position trees", journal = j-SIAM-J-COMPUT, volume = "9", number = "4", pages = "785--807", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68E10", MRnumber = "82a:68124", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Coffman:1980:PBL, author = "E. G. {Coffman, Jr.} and M. R. Garey and D. S. Johnson and R. E. Tarjan", title = "Performance bounds for level-oriented two-dimensional packing algorithms", journal = j-SIAM-J-COMPUT, volume = "9", number = "4", pages = "808--826", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (52A45 90B99)", MRnumber = "82a:68068", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Aspvall:1980:PTA, author = "Bengt Aspvall and Yossi Shiloach", title = "A polynomial time algorithm for solving systems of linear inequalities with two variables per inequality", journal = j-SIAM-J-COMPUT, volume = "9", number = "4", pages = "827--845", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C05 (65F30 68B10 90C05)", MRnumber = "82a:68052", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Baker:1980:OPT, author = "Brenda S. Baker and E. G. {Coffman, Jr.} and Ronald L. Rivest", title = "Orthogonal packings in two dimensions", journal = j-SIAM-J-COMPUT, volume = "9", number = "4", pages = "846--855", month = "????", year = "1980", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (90C25)", MRnumber = "81m:68034", MRreviewer = "D. J. Kleitman", bibdate = "Sat Jan 18 18:03:50 MST 1997", bibsource = "Graphics/siggraph/80.bib", acknowledgement = ack-nhfb, oldlabel = "geom-2886", } @Article{Fredman:1981:LBC, author = "Michael L. Fredman", title = "Lower bounds on the complexity of some optimal data structures", journal = j-SIAM-J-COMPUT, volume = "10", number = "1", pages = "1--10", month = "????", year = "1981", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68E05 (68H05)", MRnumber = "83b:68072", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Lubiw:1981:SNC, author = "Anna Lubiw", title = "Some {NP}-complete problems similar to graph isomorphism", journal = j-SIAM-J-COMPUT, volume = "10", number = "1", pages = "11--21", month = "????", year = "1981", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "03D15 (05C99 68C25 68E10)", MRnumber = "82f:03036", MRreviewer = "Egon B{\"o}rger", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Ibarra:1981:CPF, author = "Oscar H. Ibarra and Brian S. Leininger", title = "Characterizations of {Presburger} functions", journal = j-SIAM-J-COMPUT, volume = "10", number = "1", pages = "22--39", month = "????", year = "1981", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68B10 (03D20 68B05)", MRnumber = "82k:68008", bibdate = "Tue May 13 16:45:52 1997", acknowledgement = ack-nhfb, } @Article{Ehrenfeucht:1981:ESF, author = "A. Ehrenfeucht and G. Rozenberg and D. Vermeir", title = "On {ETOL} systems with finite tree-rank", journal = j-SIAM-J-COMPUT, volume = "10", number = "1", pages = "40--58", month = "????", year = "1981", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68F05", MRnumber = "83c:68091", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Rowland:1981:STD, author = "John H. Rowland and Philip J. Davis", title = "On the selection of test data for recursive mathematical subroutines", journal = j-SIAM-J-COMPUT, volume = "10", number = "1", pages = "59--72", month = "????", year = "1981", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "65Q05 (39A10 68B10)", MRnumber = "82m:65116", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Lee:1981:GVD, author = "D. T. Lee and R. L. {Drysdale, III}", title = "Generalization of {Vorono{\u{\i}}} diagrams in the plane", journal = j-SIAM-J-COMPUT, volume = "10", number = "1", pages = "73--87", month = feb, year = "1981", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "90B05 (05C10 51-04 68E10)", MRnumber = "83i:90048", MRreviewer = "Frank K. Hwang", bibdate = "Thu Jan 23 10:52:45 1997", bibsource = "Graphics/siggraph/81.bib, Neural/adapt.sys.bib, Ai/adapt.sys.bib, Graphics/siggraph/81.bib", acknowledgement = ack-nhfb, keywords = "Vorono{\u{\i}} diagrams, line segments, two-dimensional", oldlabel = "geom-347, geom-166.2", ref = "VV36", succeeds = "dl-gvdp-78", } @Article{Ellis:1981:FSW, author = "Martin H. Ellis and J. Michael Steele", title = "Fast sorting of {Weyl} sequences using comparisons", journal = j-SIAM-J-COMPUT, volume = "10", number = "1", pages = "88--95", month = "????", year = "1981", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68E05 (10K05 68C25)", MRnumber = "82k:68030", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Bennett:1981:RRO, author = "Charles H. Bennett and John Gill", title = "Relative to a random oracle ${A}$, ${\bf P}^{A}\not={\bf NP}^{A}\not={\rm co}-{\bf NP}^{A}$ with probability $1$", journal = j-SIAM-J-COMPUT, volume = "10", number = "1", pages = "96--113", month = "????", year = "1981", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (03D15)", MRnumber = "83a:68044", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Jones:1981:NCG, author = "Neil D. Jones and Sven Skyum", title = "A note on the complexity of general {DOL} membership", journal = j-SIAM-J-COMPUT, volume = "10", number = "1", pages = "114--117", month = "????", year = "1981", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (68D22)", MRnumber = "83a:68048", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Liu:1981:SPM, author = "Ken Chih Liu", title = "On string pattern matching: a new model with a polynomial time algorithm", journal = j-SIAM-J-COMPUT, volume = "10", number = "1", pages = "118--140", month = "????", year = "1981", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (68G10)", MRnumber = "83c:68050", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Ruskey:1981:LCS, author = "Frank Ruskey", title = "Listing and counting subtrees of a tree", journal = j-SIAM-J-COMPUT, volume = "10", number = "1", pages = "141--150", month = "????", year = "1981", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68E10 (05C05)", MRnumber = "82j:68066", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Kunde:1981:NLS, author = "Manfred Kunde", title = "Nonpreemptive {LP}-scheduling on homogeneous multiprocessor systems", journal = j-SIAM-J-COMPUT, volume = "10", number = "1", pages = "151--173", month = "????", year = "1981", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C15 (90B35)", MRnumber = "83a:68040", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Reghizzi:1981:OPG, author = "Stefano Crespi-Reghizzi and Giovanni Guida and Dino Mandrioli", title = "Operator precedence grammars and the noncounting property", journal = j-SIAM-J-COMPUT, volume = "10", number = "1", pages = "174--191", month = "????", year = "1981", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68F05", MRnumber = "83e:68100", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Dessouky:1981:SJU, author = "M. I. Dessouky and J. S. Deogun", title = "Sequencing Jobs with Unequal Ready Times to Minimize Mean Flow Time", journal = j-SIAM-J-COMPUT, volume = "10", number = "1", pages = "192--202", month = feb, year = "1981", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C15 (90B35)", MRnumber = "83b:68022", bibdate = "Sat Jan 18 18:03:50 MST 1997", bibsource = "Database/Graefe.bib", acknowledgement = ack-nhfb, } @Article{Colbourn:1981:LTA, author = "Charles J. Colbourn and Kellogg S. Booth", title = "Linear time automorphism algorithms for trees, interval graphs, and planar graphs", journal = j-SIAM-J-COMPUT, volume = "10", number = "1", pages = "203--225", month = "????", year = "1981", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68E10 (05C99 68C25)", MRnumber = "82k:68034", MRreviewer = "T. R. S. Walsh", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Flon:1981:TCP, author = "Lawrence Flon and Norihisa Suzuki", title = "The total correctness of parallel programs", journal = j-SIAM-J-COMPUT, volume = "10", number = "2", pages = "227--246", month = "????", year = "1981", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68B10 (03D80)", MRnumber = "84c:68006", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Katoh:1981:AFM, author = "N. Katoh and T. Ibaraki and H. Mine", title = "An algorithm for finding ${K}$ minimum spanning trees", journal = j-SIAM-J-COMPUT, volume = "10", number = "2", pages = "247--255", month = "????", year = "1981", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68E10 (05C05 68C25)", MRnumber = "82k:68037", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Garey:1981:SUT, author = "M. R. Garey and D. S. Johnson and B. B. Simons and R. E. Tarjan", title = "Scheduling unit-time tasks with arbitrary release times and deadlines", journal = j-SIAM-J-COMPUT, volume = "10", number = "2", pages = "256--269", month = may, year = "1981", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C15 (90B35)", MRnumber = "83c:68037", MRreviewer = "Jan W\polhk eglarz", bibdate = "Sat Jan 18 18:03:50 MST 1997", bibsource = "Misc/Discrete.event.bib", acknowledgement = ack-nhfb, } @Article{Frederickson:1981:AAS, author = "Greg N. Frederickson and Joseph Ja'Ja'", title = "Approximation algorithms for several graph augmentation problems", journal = j-SIAM-J-COMPUT, volume = "10", number = "2", pages = "270--283", month = "????", year = "1981", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (03D15 05C40 68E10)", MRnumber = "83b:68045", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Boasson:1981:RIC, author = "Luc Boasson and Bruno Courcelle and Maurice Nivat", title = "The rational index: a complexity measure for languages", journal = j-SIAM-J-COMPUT, volume = "10", number = "2", pages = "284--296", month = "????", year = "1981", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68F05 (03D05 03D15 68C25)", MRnumber = "83b:68078", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Yannakakis:1981:EDP, author = "Mihalis Yannakakis", title = "Edge-deletion problems", journal = j-SIAM-J-COMPUT, volume = "10", number = "2", pages = "297--309", month = "????", year = "1981", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (05C35 68E10)", MRnumber = "83b:68039", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Yannakakis:1981:NDP, author = "M. Yannakakis", title = "Node-deletion problems on bipartite graphs", journal = j-SIAM-J-COMPUT, volume = "10", number = "2", pages = "310--327", month = "????", year = "1981", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (05C35 68E10)", MRnumber = "83b:68040", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Megiddo:1981:ATN, author = "N. Megiddo and A. Tamir and E. Zemel and R. Chandrasekaran", title = "An {$O(n (\log^{2} n))$} algorithm for the {$k$}-th nearest pair in a tree with applications to location problems", journal = j-SIAM-J-COMPUT, volume = "10", number = "2", pages = "328--337", month = may, year = "1981", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68E10 (68C25 90B05)", MRnumber = "82j:68063", bibdate = "Thu Jan 23 10:53:42 1997", bibsource = "Graphics/siggraph/81.bib", acknowledgement = ack-nhfb, keywords = "complexity theory, network algorithms, optimization, searching, centroid decomposition", oldlabel = "geom-906", xxtitle = "An ${O}(n\,{\rm log}^{2}\,n)$ algorithm for the $k$th longest path in a tree with applications to location problems", } @Article{Lueker:1981:OPG, author = "George S. Lueker", title = "Optimization problems on graphs with independent random edge weights", journal = j-SIAM-J-COMPUT, volume = "10", number = "2", pages = "338--351", month = "????", year = "1981", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "90C35 (05C35 60C05)", MRnumber = "83a:90169", MRreviewer = "James R. Evans", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Beeri:1981:ERD, author = "Catriel Beeri and Alberto O. Mendelzon and Yehoshua Sagiv and Jeffrey D. Ullman", title = "Equivalence of Relational Database Schemes", journal = j-SIAM-J-COMPUT, volume = "10", number = "2", pages = "352--370", month = may, year = "1981", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68B15", MRnumber = "82m:68033", bibdate = "Sat Jan 18 18:03:50 MST 1997", bibsource = "Database/Wiederhold.bib", acknowledgement = ack-nhfb, annote = "reduced to equivalence of fixed-point join-project mappings, that satisfy given dependencies. Polynomial algorithms to test without dependencies, and to test of if a mapping with dependencies preserves functional dependencies. Irreducible update sets.", } @Article{Schnorr:1981:ESD, author = "C.-P. Schnorr", title = "An extension of {Strassen}'s degree bound", journal = j-SIAM-J-COMPUT, volume = "10", number = "2", pages = "371--382", month = "????", year = "1981", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (03D15 12-04 14-04)", MRnumber = "83b:68054", bibdate = "Fri Oct 27 15:21:50 2000", acknowledgement = ack-nhfb, } @Article{Hartmanis:1981:LSC, author = "J. Hartmanis and S. Mahaney", title = "Languages simultaneously complete for one-way and two-way log-tape automata", journal = j-SIAM-J-COMPUT, volume = "10", number = "2", pages = "383--390", month = "????", year = "1981", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68F10 (03D05 68D05)", MRnumber = "83m:68147", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Proskurowski:1981:RGR, author = "Andrzej Proskurowski", title = "Recursive graphs, recursive labelings and shortest paths", journal = j-SIAM-J-COMPUT, volume = "10", number = "2", pages = "391--397", month = "????", year = "1981", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68E10 (05C99)", MRnumber = "82j:68065", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Yao:1981:AMA, author = "Andrew C. Yao", title = "An analysis of a memory allocation scheme for implementing stacks", journal = j-SIAM-J-COMPUT, volume = "10", number = "2", pages = "398--403", month = "????", year = "1981", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25", MRnumber = "83b:68056", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Aho:1981:ITL, author = "A. V. Aho and Y. Sagiv and T. G. Szymanski and J. D. Ullman", title = "Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions", journal = j-SIAM-J-COMPUT, volume = "10", number = "3", pages = "405--421", month = "????", year = "1981", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68B15 (68C05)", MRnumber = "82h:68015", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Gotlieb:1981:OMS, author = "L. Gotlieb", title = "Optimal multiway search trees", journal = j-SIAM-J-COMPUT, volume = "10", number = "3", pages = "422--433", month = "????", year = "1981", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C05 (68C25)", MRnumber = "82h:68047", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Schonhage:1981:PTM, author = "A. Sch{\"o}nhage", key = "Schonhage", title = "Partial and Total Matrix Multiplication", journal = j-SIAM-J-COMPUT, volume = "10", number = "3", pages = "434--455", month = aug, year = "1981", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68C25 (03D15 65F30)", MRnumber = "82h:68070", bibdate = "Thu Jan 23 10:53:58 1997", bibsource = "Parallel/Multi.bib", acknowledgement = ack-nhfb, } @Article{Schroeppel:1981:OOA, author = "Richard Schroeppel and Adi Shamir", title = "A ${T}={O}(2^{n/2})$, ${S}={O}(2^{n/4})$ algorithm for certain {NP}-complete problems", journal = j-SIAM-J-COMPUT, volume = "10", number = "3", pages = "456--464", month = "????", year = "1981", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "90C10 (68C25)", MRnumber = "83a:90116", MRreviewer = "G. {\v{S}}erk{\v{s}}nys", bibdate = "Sat Jan 18 18:03:50 MST 1997", acknowledgement = ack-nhfb, } @Article{Haggkvist:1981:PSC, author = "Roland H{\"a}ggkvist and Pavol Hell", title = "Parallel sorting with constant time for comparisons", journal = j-SIAM-J-COMPUT, volume = "10", number = "3", pages = "465--472", month = "????", year = "1981", CODEN = "SMJCAT", ISSN = "0097-5397 (print), 1095-7111 (electronic)", MRclass = "68E05 (05C20)", MRnumber = "8