% File: ALGORITHMS.BIB
% (Modified version of /a/clr/1.2/book.bib
% Created 12/11/87 by RLR
% This file contains references for our book in BIBTEX format, as described
% on pages 140--147 of the Latex manual.
%
% The key for an entry should be the concatenation of:
% (1) The full last name of the first author (first letter capitalized),
% (2) The first two characters of the last name of each following
% author (first letter capitalized),
% (3) The last two digits of the year of the publication, and
% (4) [Optional] A letter from "bcdefg..." or other text (e.g. volume
% number) if necessary to yield unique keys.
%
% Example: AhoHoUl74
%
% The entries in this file should be alphabetically sorted by key value.
%
% A citation in the Latex source will have the form \cite{AhoHoUl74}.
%
% According to Larry Cohen of MIT Press, use author names exactly
% as they appear in the cited works, with the following exceptions:
% (1) Each individual should have his/her name cited exactly the same way
% everywhere in bibliography. (2) Do not use full middle names; use
% middle initials instead. To indicate the author name as it actually
% appears in the cited work when it differs from how we reference it,
% use the field "workauthor".
%
% For more examples of Bibtex database (with different key convention), see
% /th/u/rivest/papers/ai.bib.
%
% Policy decisions subject to review:
% Our bibliography style will be "plain" (see manual pg. 74).
% The \bibliographystyle{plain} needs to go just after the
% \begin{document} command in our top-level files.
% Author names should be first, then last.
% We will have all references placed at the end of the book
% (and not at the end of each chapter). However,
% the chnn.tex files will probably want to have a
% references section for debugging (as in ch31).
% Our standard reference format will be to include the author's
% name (possibly with et al.) to fill the grammatical
% part of the sentence, and then give a citation immediately
% after the name.
% Examples: "... See Knuth \cite[p. 234]{Knuth69b} for ..."
% "... Knuth \cite{Knuth69b} proves that ..."
% When there is more than one reference, we give multiple
% \cite commands: \cite{Knuth69}, \cite{Wilf86}.
%
% To use Bibtex:
% "latex book" once to get the citations into book.aux.
% "bibtex book" to get the references from book.bib into book.bbl.
% "latex book" again to get the first pass bibliography made.
% "latex book" again to get the labels right.
% The "plain" style gives us 3-letter month abbreviations (lowercase,
% e.g., sep is "September").
% If we want to keep the month in this file but don't want it to print
% (e.g., because volume:number is sufficient), use mon instead of month.
% Similarly, replace "address" by "addr".
% \sortby allows us to define how entries are sorted.
% Example: title = "{\sortby{a}}First title, which should go first"
% and in another entry,
% title = "{\sortby{b}}Another title, which would otherwise go first"
@preamble{
"\newcommand{\sortby}[1]{}"
}
% Abbreviations for journals, proceedings, etc.
% The "plain" style gives us the following journals:
% acmcs ACM Computing Surveys
% acta Acta Informatica
% cacm Communications of the ACM
% ieeetc IEEE Transactions on Computers
% ipl Information Processing Letters
% jacm Journal of the ACM
% jcss Journal of Computer and System Sciences
% sicomp SIAM Journal on Computing
% tcs Theoretical Computer Science
@string{focs16 = "Proceedings of the 16th Annual Symposium on Foundations of Computer Science"}
@string{focs17 = "Proceedings of the 17th Annual Symposium on Foundations of Computer Science"}
@string{focs18 = "Proceedings of the 18th Annual Symposium on Foundations of Computer Science"}
@string{focs19 = "Proceedings of the 19th Annual Symposium on Foundations of Computer Science"}
@string{focs20 = "Proceedings of the 20th Annual Symposium on Foundations of Computer Science"}
@string{focs21 = "Proceedings of the 21st Annual Symposium on Foundations of Computer Science"}
@string{focs22 = "Proceedings of the 22nd Annual Symposium on Foundations of Computer Science"}
@string{focs23 = "Proceedings of the 23rd Annual Symposium on Foundations of Computer Science"}
@string{focs24 = "Proceedings of the 24th Annual Symposium on Foundations of Computer Science"}
@string{focs25 = "Proceedings of the 25th Annual Symposium on Foundations of Computer Science"}
@string{focs26 = "Proceedings of the 26th Annual Symposium on Foundations of Computer Science"}
@string{focs27 = "Proceedings of the 27th Annual Symposium on Foundations of Computer Science"}
@string{focs28 = "Proceedings of the 28th Annual Symposium on Foundations of Computer Science"}
@string{focs29 = "Proceedings of the 29th Annual Symposium on Foundations of Computer Science"}
@string{stoc1 = "Proceedings of the ACM Symposium on Theory of Computing"}
@string{stoc2 = "Proceedings of the Second Annual ACM Symposium on Theory of Computing"}
@string{stoc3 = "Proceedings of the Third Annual ACM Symposium on Theory of Computing"}
@string{stoc4 = "Proceedings of the Fourth Annual ACM Symposium on Theory of Computing"}
@string{stoc5 = "Proceedings of the Fifth Annual ACM Symposium on Theory of Computing"}
@string{stoc6 = "Proceedings of the Sixth Annual ACM Symposium on Theory of Computing"}
@string{stoc7 = "Proceedings of the Seventh Annual ACM Symposium on Theory of Computing"}
@string{stoc8 = "Proceedings of the Eighth Annual ACM Symposium on Theory of Computing"}
@string{stoc9 = "Proceedings of the Ninth Annual ACM Symposium on Theory of Computing"}
@string{stoc10 = "Proceedings of the Tenth Annual ACM Symposium on Theory of Computing"}
@string{stoc11 = "Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing"}
@string{stoc12 = "Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing"}
@string{stoc13 = "Proceedings of the Thirteenth Annual ACM Symposium on Theory of Computing"}
@string{stoc14 = "Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing"}
@string{stoc15 = "Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing"}
@string{stoc16 = "Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing"}
@string{stoc17 = "Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing"}
@string{stoc18 = "Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing"}
@string{stoc19 = "Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing"}
@string{stoc20 = "Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing"}
@string{stoc21 = "Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing"}
%=A
@book{AbramowitzSt65,
editor = "Milton Abramowitz and Irene A. Stegun",
title = "Handbook of Mathematical Functions",
publisher = "Dover",
year = 1965
}
@article{AVL62,
author = "G. M. Adel'son-Vel'ski\u{\i} and E. M. Landis",
title = "An Algorithm for the Organization of Information",
journal = "Soviet Mathematics Doklady",
volume = 3,
year = 1962,
pages = "1259--1263"}
@article{AdlemanPoRu83,
author = "Leonard M. Adleman and Carl Pomerance and Robert S. Rumely",
title = "On Distinguishing Prime Numbers from Composite Numbers",
journal = "Annals of Mathematics",
year = 1983,
volume = 117,
pages = "173--206"
}
@book{AhoHoUl74,
author = "Alfred V. Aho and John E. Hopcroft and Jeffrey D. Ullman",
title = "The Design and Analysis of Computer Algorithms",
publisher = "Addison-Wesley",
year = 1974
}
@book{AhoHoUl83,
author = "Alfred V. Aho and John E. Hopcroft and Jeffrey D. Ullman",
title = "Data Structures and Algorithms",
publisher = "Addison-Wesley",
year = 1983
}
@article{AhoStUl75,
workauthor = "A. V. Aho and K. Steiglitz and Jeffrey D. Ullman",
author = "Alfred V. Aho and Kenneth Steiglitz and Jeffrey D. Ullman",
title = "Evaluating Polynomials at Fixed Sets of Points",
journal = sicomp,
volume = 4,
number = 4,
mon = dec,
year = 1975,
pages = "533--539"
}
@techreport{AhujaMeOrTa88,
author = "Ravindra K. Ahuja and Kurt Mehlhorn and James B. Orlin and Robert E. Tarjan",
title = "Faster Algorithms for the Shortest Path Problem",
institution = "MIT Operations Research Center",
year = 1988,
mon = apr,
number = 193
}
% Unreferenced
@techreport{AhujaOr88,
author = "Ravindra K. Ahuja and James B. Orlin",
title = "A Fast and Simple Algorithm for the Maximum Flow Problem",
year = 1988,
month = mar,
institution = "Sloan School of Management, Massachusetts Institute of Technology",
number = "1905-87",
note = "To appear in {\it Operations Research}."
}
% Unreferenced
@article{AhujaOrTa89,
author = "Ravindra K. Ahuja and James B. Orlin and Robert E. Tarjan",
title = "Improved Time Bounds for the Maximum Flow Problem",
journal = sicomp,
year = 1989,
mon = oct,
volume = 18,
number = 5,
pages = "939--954"
}
@incollection{AikenHopper46,
author = "Howard H. Aiken and Grace M. Hopper",
title = "The Automatic Sequence Controlled Calculator",
booktitle = "The Origins of Digital Computers",
publisher = "Springer-Verlag",
year = 1982,
pages = "203--222",
editor = "Brian Randell",
edition = "Third"
}
@inproceedings{AjtaiKoSz83,
author = "M. Ajtai and J. Koml\'os and E. Szemer\'edi",
title = "An {$O(n \log n)$} Sorting Network",
booktitle = stoc15,
year = 1983,
mon = apr,
pages = "1--9"
}
@book{Akl89,
author = "Selim G. Akl",
title = "The Design and Analysis of Parallel Algorithms",
publisher = "Prentice-Hall",
year = 1989
}
% From Gary.
@inproceedings{AndersonMi88b,
author = "Richard J. Anderson and Gary L. Miller",
title = "Deterministic Parallel List Ranking",
booktitle = "1988 Aegean Workshop on Computing",
series = "Lecture Notes in Computer Science",
volume = 319,
publisher = "Springer-Verlag",
editor = "John H. Reif",
pages = "81--90",
year = 1988
}
% From Gary. Apparently has not appeared.
@unpublished{AndersonMi88a,
author = "Richard J. Anderson and Gary L. Miller",
title = "A Simple Randomized Parallel Algorithm for List-Ranking",
note = "Unpublished manuscript",
year = 1988
}
@book{Apostol67,
author = "Tom M. Apostol",
title = "Calculus",
edition = "Second",
publisher = "Blaisdell Publishing Company",
year = 1967,
volume = "1"
}
@article{Atrubin65,
author = "A. J. Atrubin",
title = "A One-Dimensional Real-Time Iterative Multiplier",
journal = "IEEE Transactions on Electronic Computers",
year = 1965,
volume = "EC-14",
number = 1,
mon = feb,
pages = "394--399"
}
%=B
@book{Baase88,
author = "Sara Baase",
title = "Computer Algorithms: Introduction to Design and Analysis",
publisher = "Addison-Wesley",
year = 1988,
edition = "Second"
}
% Unreferenced.
% Check note with Ron.
@techreport{Bach89,
author = "Eric Bach",
title = "Number-Theoretic Algorithms",
institution = "Computer Science Department, University of Wisconsin,
Madison",
year = 1989,
month = Apr,
number = 844,
note = "To appear in {\it 1989 Annual Review of Computer Science}."
}
@misc{Bach89a,
author = "Eric Bach",
howpublished = "Private communication",
year = 1989
}
% Eric Bach says this is correct. If not, we'll go to Wisconsin and
% throw cheese at him.
@incollection{Bach90,
author = "Eric Bach",
title = "Number-Theoretic Algorithms",
booktitle = "Annual Review of Computer Science",
publisher = "Annual Reviews, Inc.",
addr = "Palo Alto",
year = 1990,
volume = 4,
pages = "119--172"
}
@unpublished{Bachellis90,
author = {Bachellis, Gregory F. and Frank J. Massey III},
title = {A Coin Tossing Problem of R. L. Rivest},
year = {1990}
}
@incollection{BachellisMa90,
author = {Bachellis, Gregory F. and Frank J. Massey III},
title = {A Coin Tossing Problem of R. L. Rivest},
booktitle = {Springer Lecture Notes},
volume = 1450,
pages = {36--52},
year = {1990}
}
% reference from Knuth76 and not checked
% Unreferenced
@book{Bachmann94,
author = "Paul Bachmann",
title = "Die Analytische Zahlentheorie. Zahlentheorie, pt.\ 2",
address = "Liepzig",
publisher = "B. G. Teubner",
year = 1894
}
%% was originally keyed as Bayer71 ???
@article{Bayer72,
author = "R. Bayer",
title = "Symmetric Binary {B}-trees: {D}ata Structure and Maintenance Algorithms",
journal = acta,
volume = 1,
year = 1972,
pages = "290-306"
}
@article{BayerMc72,
author = "R. Bayer and E. M. McCreight",
title = "Organization and Maintenance of Large Ordered Indexes",
journal = acta,
year = 1972,
volume = 1,
number = 3,
pages = "173--189"
}
@article{BeameCoHo84,
title = "Log Depth Circuits For Division and Related Problems",
author = "Paul W. Beame and Stephen A. Cook and H. James Hoover",
journal = sicomp,
year = 1986,
volume = 15,
number = 4,
pages = "994--1003",
mon = nov
}
@article{BeaucheminBrCrGoPo88,
author = "Pierre Beauchemin and Gilles Brassard and
Claude Cr\'epeau and Claude Goutier and
Carl Pomerance",
title = "The Generation of Random Numbers That Are Probably Prime",
journal = "Journal of Cryptology",
year = 1988,
volume = 1,
pages = "53--64"
}
@book{Bellman57,
author = "Richard Bellman",
title = "Dynamic Programming",
year = 1957,
publisher = "Princeton University Press",
addr = "Princeton, New Jersey"
}
@article{Bellman58,
author = "Richard Bellman",
title = "On a Routing Problem",
journal = "Quarterly of Applied Mathematics",
year = 1958,
volume = 16,
number = 1,
pages = "87--90"
}
@inproceedings{Ben-Or83,
author = "Michael {Ben-Or}",
title = "Lower Bounds for Algebraic Computation Trees",
booktitle = stoc15,
year = 1983,
pages = "80--86"
}
@book{Bentley82,
workauthor = "Jon Louis Bentley",
author = "Jon L. Bentley",
title = "Writing Efficient Programs",
publisher = "Prentice-Hall",
year = 1982
}
@article{Bentley75,
author = "Jon L. Bentley",
title = "Multidimensional Binary Search Trees Used fro Associative Searching",
journal = cacm,
year = 1975,
mon = sept,
volume = 19,
pages = "509--517"
}
@article{Bentley79,
author = "Jon L. Bentley",
title = "Multidimensional Binary Search Trees in Database Applications",
journal = "IEEE Transactions on Software Engineering",
year = 1979,
mon = july,
volume = 5,
number = 4,
pages = "333--340"
}
% Unreferenced
@article{Bentley84,
author = "Jon L. Bentley",
title = "Programming Pearls: {H}ow to Sort",
journal = cacm,
year = 1984,
mon = apr,
volume = 27,
number = 4,
pages = "287--291"
}
@book{Bentley86,
workauthor = "Jon Bentley",
author = "Jon L. Bentley",
title = "Programming Pearls",
publisher = "Addison-Wesley",
year = 1986
}
@article{BentleyHaSa80,
author = "Jon L. Bentley and Dorothea Haken and James B. Saxe",
title = "A General Method For Solving Divide-and-conquer Recurrences",
journal = "SIGACT News",
year = 1980,
volume = 12,
number = 3,
pages = "36--44"
}
@article{BentleyOt79,
author = "Jon L. Bentley and Thomas A. Ottmann",
title = "Algorithms for Reporting and Counting Geometric Intersections",
journal = cacm,
year = 1979,
mon = sep,
volume = 28,
number = 9,
pages = "643--647"
}
@book{Beyer89,
editor = "William H. Beyer",
title = "CRC Standard Mathematical Tables",
publisher = "The Chemical Rubber Company",
year = 1984
}
@book{Billingsley86,
author = "Patrick Billingsley",
title = "Probability and Measure",
publisher = "John Wiley \& Sons",
year = "1986",
edition = "Second"
}
% Unreferenced
@phdthesis{Blelloch89,
author = "Guy E. Blelloch",
title = "Scan Primitives and Parallel Vector Models",
school = "Department of Electrical Engineering and Computer Science, MIT",
year = 1989,
month = oct,
note = "Available as MIT Laboratory for Computer Science Technical Report MIT/LCS/TR-363."
}
@article{Bluestein70,
author = "L. I. Bluestein",
title = "A Linear Filtering Approach to the Computation of the
Discrete {F}ourier Transform",
journal = "IEEE Transactions on Electroacoustics",
volume = "AU-18",
year = 1970,
pages = "451--455"
}
@article{BlumFlPrRiTa73,
author = "Manuel Blum and Robert W. Floyd and Vaughan Pratt and
Ronald L. Rivest and Robert E. Tarjan",
title = "Time Bounds for Selection",
journal = jcss,
year = 1973,
mon = aug,
volume = 7,
number = 4,
pages = "448--461"
}
% Unreferenced
@inproceedings{BlumKa89,
author = "M. Blum and S. Kannan",
title = "Programs That Check Their Work",
booktitle = stoc21,
year = 1989
}
@book{Bollobas85,
author = "B\'ela Bollob\'as",
title = "Random Graphs",
publisher = "Academic Press",
year = 1985
}
% From Tarjan
% Unreferenced
@article{Boruvka26,
author = "Bor\.{u}vka, O.",
title = "O jist\'{e}m probl\'{e}mu minim\'{a}ln\'{\i}m",
journal = "Pr\'{a}ce Moravsk\'{e} P\v{r}\'{\i}rodov\v{e}deck\'{e}
Spole\v{c}nosti",
volume = 3,
year = 1926,
pages = "37--58",
note = "In Czech."
}
@article{BoyerMo77,
author = "Robert S. Boyer and J. Strother Moore",
title = "A Fast String-Searching Algorithm",
journal = cacm,
year = "1977",
mon = oct,
volume = 20,
number = 10,
pages = "762--772"
}
% breakedit
@book{BrassardBr88,
author = "Gilles Brassard and Paul Bratley",
title = "Algorithmics: Theory and Practice",
publisher = "Pren\-tice-Hall",
year = 1988
}
@book{BondyMu76,
author = "J. A. Bondy and U. S. R. Murty",
title = "Graph Theory with Applications",
publisher = "American Elsevier",
year = 1976
}
@article{Brent74,
author = "Richard P. Brent",
title = "The Parallel Evaluation of General Arithmetic Expressions",
journal = jacm,
volume = 21,
number = 2,
mon = apr,
year = 1974,
pages = "201--206"
}
@article{Brent80,
author = "Richard P. Brent",
title = "An Improved {M}onte {C}arlo Factorization Algorithm",
journal = "BIT",
volume = 20,
number = 2,
year = 1980,
pages = "176--184"
}
% Unreferenced
@book{BronshteinSe85,
author = "I. N. Bronshtein and K. A. Semendyayev",
title = "Handbook of Mathematics",
year = 1985,
publisher = "Van Nostrand Reinhold Company",
note = "English translation edited by K.~A. Hirsch."
}
@phdthesis{Brown77,
author = "Mark R. Brown",
title = "The Analysis of a Practical and Nearly Optimal Priority Queue",
school = "Computer Science Department, Stanford University",
year = 1977,
mon = mar,
note = "Technical Report STAN-CS-77-600."
}
@article{Brown78,
author = "Mark R. Brown",
title = "Implementation and Analysis of Binomial Queue Algorithms",
journal = sicomp,
year = 1978,
mon = aug,
volume = 7,
number = 3,
pages = "298--319"
}
@book{Burks66,
editor = "Arthur W. Burks",
title = "Theory of Self-Reproducing Automata",
publisher = "University of Illinois Press",
year = 1966
}
%=C
% Unreferenced
@article{CarterWe79,
author = "J. L. Carter and M. N. Wegman",
title = "Universal Classes of Hash Functions",
journal = jcss,
year = 1979,
mon = apr,
volume = 18,
number = 2,
pages = "143--154"
}
@book{Cavanagh84,
author = "Joseph J. F. Cavanagh",
title = "Digital Computer Arithmetic",
publisher = "McGraw-Hill",
year = 1984
}
% Unreferenced
@article{ChazelleGuLe85,
author = "Bernard Chazelle and Leo.\ J. Guibas and D. T. Lee",
title = "The Power of Geometric Duality",
journal = "BIT",
volume = 25,
number = 1,
year = 1985,
pages = "76--90"
}
% Unreferenced
@inproceedings{ChazelleEd88,
author = "Bernard Chazelle and Herbert Edelsbrunner",
title = "An Optimal Algorithm for Intersecting Line Segments in the Plane",
booktitle = focs29,
publisher = "IEEE Computer Society",
year = 1988,
pages = "590--600"
}
% Unreferenced
@unpublished{CheriyanMa87,
author = "J. Cheriyan and S. N. Maheshwari",
title = "Analysis of Preflow Push Algorithms for Maximum Network
Flow",
year = 1987,
month = aug,
note = "Department of Computer Science and Engineering,
Indian Institute of Technology,
New Delhi, India"
}
% Unreferenced
@article{Cherkasky77,
author = "R. V. Cherkasky",
title = "Algorithm of Construction of Maximal Flow in Networks with Complexity of {$O(V^2 \sqrt{E})$} Operations",
journal = "Mathematical Methods of Solution of Economical Problems",
year = 1977,
volume = 7,
pages = "112--125",
note = "In Russian."
}
@article{Chernoff52,
author = "H. Chernoff",
title = "A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations",
journal = "Annals of Mathematical Statistics",
volume = 23,
year = 1952,
pages = "493--507"
}
@article{ChorLeRiSh86,
author = {B. Chor and C. E. Leiserson and R. L. Rivest and J. Shearer},
title = {An application of Number Theory to the Organization of Raster Graphics},
journal = {Journal of the ACM},
volume = 33,
number = 1,
year = 1986,
month = Jan,
pages = {86--104}
}
@book{Chung74,
author = "Kai Lai Chung",
title = "Elementary Probability Theory with Stochastic Processes",
publisher = "Springer-Verlag",
year = 1974
}
@article{Chvatal79,
author = "V. Chv\'atal",
title = "A Greedy Heuristic for the Set-Covering Problem",
journal = "Mathematics of Operations Research",
volume = 4,
number = 3,
year = 1979,
mon = aug,
pages = "233--235"
}
@techreport{ChvatalKlKn72,
author = "V. Chv\'{a}tal and D. A. Klarner and D. E. Knuth",
title = "Selected Combinatorial Research Problems",
mon = jun,
year = 1972,
institution = "Computer Science Department, Stanford University",
number = "STAN-CS-72-292"
}
@inproceedings{Cobham64,
author = "Alan Cobham",
title = "The Intrinsic Computational Difficulty of Functions",
booktitle = "Proceedings of the 1964 Congress for Logic, Methodology,
and the Philosophy of Science",
publisher = "North-Holland",
year = 1964,
pages = "24--30"
}
% Unreferenced
@book{Cohen78,
author = "Daniel I. A. Cohen",
title = "Basic Techniques of Combinatorial Theory",
publisher = "John Wiley \& Sons",
year = 1978
}
@article{CohenLe84,
author = "H. Cohen and Lenstra, Jr., H. W.",
title = "Primality Testing and Jacobi Sums",
journal = "Mathematics of Computation",
year = "1984",
volume = 42,
number = 165,
mon = jan,
pages = "297--330"
}
% Unreferenced.
% Implements AdlemanPoRu...
@article{CohenLe87,
author = "H. Cohen and A. K. Lenstra",
title = "Implementation of a new primality test",
journal = "Mathematics of Computation",
volume = 48,
year = 1987,
pages = "103--121"
}
@inproceedings{Cole86,
author = "Richard Cole",
title = "Parallel Merge Sort",
booktitle = focs27,
publisher = "IEEE Computer Society",
year = 1986,
pages = "511--516"
}
@article{ColeVi86,
author = "Richard Cole and Uzi Vishkin",
title = "Deterministic Coin Tossing with Applications to Optimal
Parallel List Ranking",
journal = "Information and Control",
volume = 70,
number = 1,
mon = july,
year = 1986,
pages = "32--53"
}
@article{Comer79,
author = "D. Comer",
title = "The Ubiquitous {B}-tree",
journal = acmcs,
year = 1979,
mon = Jun,
volume = 11,
number = 2,
pages = "121--137"
}
% breakedit
@article{CoTu65,
author = "James W. Cooley and John W. Tukey",
title = "An Algorithm for the Machine Calculation of Complex {F}ourier Series",
journal = "Mathematics of Computation",
volume = 19,
number = 90,
month = apr,
year = 1965,
pages = "\linebreak[4]297--301"
}
@inproceedings{CoppersmithWi87,
author = "Don Coppersmith and Shmuel Winograd",
title = "Matrix Multiplication via Arithmetic Progressions",
booktitle = stoc19,
year = 1987,
pages = "1--6"
}
% Re: Matrix Multiplication
% ***** Reply to your file: RIVEST MAIL of: 08/07 15:38:56 *****************
% Ron, the STOC paper is the only published version.
% We submitted it to a special issue of J. Symb. ???? (either Alg. or Comp.,
% I can never remember which), edited by Eric Kaltoffen, and this isn't
% due out until May 1990. 2.376 is still the number.
% Don
@inproceedings{Cook71,
workauthor = "Stephen A. Cook",
author = "Stephen Cook",
title = "The Complexity of Theorem Proving Procedures",
booktitle = stoc3,
year = 1971,
pages = "151--158"
}
@article{CookDwRe86,
author = {Stephen Cook and Cynthia Dwork and R\"{u}diger Reischuk},
title = "Upper and Lower Time Bounds For Parallel Random Access Machines Without Simultaneous Writes",
journal = sicomp,
volume = 15,
number = 1,
mon = feb,
year = 1986,
pages = "87--97"
}
@book{CormenLeRi90,
author = {Cormen, Thomas H. and Charles E. Leiserson and
Ronald L. Rivest},
title = {Introduction to Algorithms},
publisher = {MIT Press/McGraw-Hill},
year = 1990
}
%=D
% Unreferenced
% From Press et al.
@article{DanielsonLa42,
author = "G. C. Danielson and C. Lanczos",
title = "Some Improvements in Practical {F}ourier Analysis
and Their Application to {X}-ray Scattering from
Liquids",
journal = "J. Franklin Institute",
year = 1942,
volume = 233,
pages = "365--380 and 435--452"
}
@inbook{Dantzig51,
author = "George B. Dantzig",
chapter = "Programming of Interdependent Activities, II, Mathematical
Models",
title = "Activity Analysis of Production and Allocation",
publisher = "John Wiley and Sons Inc., New York",
pages = "19--32",
year = 1951
}
@book{Dantzig63,
author = "George B. Dantzig",
title = "Linear Programming and Extensions",
publisher = "Princeton University Press",
year = 1963
}
@article{DiffieHe76,
author = "Whitfield Diffie and Martin E. Hellman",
title = "New Directions in Cryptography",
journal = "IEEE Transactions on Information Theory",
volume = "IT-22",
number = 6,
year = 1976,
mon = nov,
pages = "644--654"
}
@article{Dijkstra59,
author = "E. W. Dijkstra",
title = "A Note on Two Problems in Connexion with Graphs",
journal = "Numerische Mathematik",
volume = 1,
year = 1959,
pages = "269--271"
}
% Unreferenced
@article{Dinic70,
author = "E. A. Dinic",
title = "Algorithm for Solution of a Problem of Maximum Flow in Networks with Power Estimation",
journal = "Soviet Mathematics Doklady",
volume = 11,
year = 1970,
pages = "1277--1280"
}
@article{Dixon84,
author = "John D. Dixon",
title = "Factorization and Primality Tests",
journal = "The American Mathematical Monthly",
year = 1984,
mon = "June--July",
volume = 91,
number = 6,
pages = "333--352"
}
@book{Drake67,
author = "Alvin W. Drake",
title = "Fundamentals of Applied Probability Theory",
publisher = "McGraw-Hill",
year = 1967
}
@article{DriscollGaShTa88,
author = "James R. Driscoll and Harold N. Gabow and
Ruth Shrairman and Robert E. Tarjan",
title = "Relaxed Heaps: {A}n Alternative to {F}ibonacci Heaps With Applications to Parallel Computation",
journal = cacm,
year = 1988,
volume = 31,
number = 11,
mon = nov,
pages = "1343--1354"
}
@inproceedings{DriscollSaSlTa86,
author = "James R. Driscoll and Neil Sarnak and Daniel D. Sleator and
Robert E. Tarjan",
title = "Making Data Structures Persistent",
booktitle = stoc18,
year = 1986,
mon = may,
pages = "109--121"
}
%=E
% Unreferenced
@article{EdelsbrunnerORSe86,
author = "H. Edelsbrunner and J. O'Rourke and R. Seidel",
title = "Constructing Arrangements of Lines and Hyperplanes with Applications",
journal = sicomp,
volume = 15,
number = 2,
mon = may,
year = 1986,
pages = "341--363"
}
@book{Edelsbrunner87,
author = "Herbert Edelsbrunner",
title = "Algorithms in Combinatorial Geometry",
publisher = "Springer-Verlag",
year = 1987,
series = "EATCS Monographs on Theoretical Computer Science",
volume = 10
}
@article{Edmonds65,
author = "Jack Edmonds",
title = "Paths, Trees, and Flowers",
journal = "Canadian Journal of Mathematics",
volume = 17,
year = 1965,
pages = "449--467"
}
@article{Edmonds71,
author = "Jack Edmonds",
title = "Matroids and the Greedy Algorithm",
journal = "Mathematical Programming",
year = 1971,
volume = 1,
pages = "126--136"
}
@article{EdmondsKa72,
workauthor = "J. Edmonds and R. M. Karp",
author = "Jack Edmonds and Richard M. Karp",
title = "Theoretical Improvements in the Algorithmic Efficiency for Network Flow Problems",
journal = jacm,
volume = 19,
year = 1972,
pages = "248--264"
}
@article{EstrinGiPo56,
author = "G. Estrin and B. Gilchrist and J. H. Pomerene",
title = "A Note on High-speed Digital Multiplication",
journal = "IRE Transactions on Electronic Computers",
volume = 5,
number = 3,
mon = sep,
year = 1956,
pages = 140
}
@book{Even79,
author = "Shimon Even",
title = "Graph Algorithms",
publisher = "Computer Science Press",
year = 1979
}
%=F
@book{Feller68,
author = "William Feller",
title = "An Introduction to Probability Theory and Its Applications",
publisher = "John Wiley \& Sons",
year = 1968,
edition = "Third"
}
@article{FinkelBe74,
author = "R. A. Finkel and J. L. Bentley",
title = "Quad-trees; a data structure for retrieval on composite keys",
journal = acta,
volume = 4,
year = 1974,
pages = "1--9"
}
@inproceedings{FischerMe71,
author = "M. J. Fischer and A. R. Meyer",
title = "Boolean Matrix Multiplication and Transitive Closure",
booktitle = "Proceedings of the Twelfth Annual Symposium on Switching
and Automata Theory",
mon = oct,
publisher = "IEEE Computer Society",
year = 1971,
pages = "129--131"
}
@article{Floyd62,
author = "Robert W. Floyd",
title = "Algorithm 97 ({SHORTEST PATH})",
journal = cacm,
volume = 5,
number = 6,
year = 1962,
pages = 345,
mon = jun
}
@article{Floyd64,
author = "Robert W. Floyd",
title = "Algorithm 245 ({TREESORT})",
journal = cacm,
volume = 7,
year = 1964,
pages = 701
}
@article{FloydRi75,
author = "Robert W. Floyd and Ronald L. Rivest",
title = "Expected Time Bounds for Selection",
journal = cacm,
year = 1975,
mon = mar,
volume = 18,
number = 3,
pages = "165--172"
}
@book{FordFu62,
workauthor = "Ford, {Jr.,}, L. R. and D. R. Fulkerson",
author = "Ford, {Jr.,}, Lestor R. and D. R. Fulkerson",
title = "Flows in Networks",
publisher = "Princeton University Press",
year = 1962
}
@article{FordJo59,
author = "Ford, {Jr.,}, Lestor R. and Selmer M. Johnson",
title = "A Tournament Problem",
journal = "The American Mathematical Monthly",
year = 1959,
volume = 66,
pages = "387--389"
}
@inproceedings{FortuneWy78,
author = "Steven Fortune and James Wyllie",
title = "Parallelism in Random Access Machines",
booktitle = stoc10,
year = 1978,
mon = may,
pages = "114--118"
}
@inproceedings{FredmanSa89,
author = "Michael L. Fredman and Michael E. Saks",
title = "The Cell Probe Complexity of Dynamic Data Structures",
booktitle = stoc21,
year = 1989,
mon = may
}
@article{FredmanTa87,
workauthor = "Michael L. Fredman and Robert Endre Tarjan",
author = "Michael L. Fredman and Robert E. Tarjan",
title = "Fibonacci Heaps and Their Uses in Improved Network
Optimization Algorithms",
journal = jacm,
volume = 34,
number = 3,
year = 1987,
mon = jul,
pages = "596--615"
}
%=G
% Unreferenced.
% Needs fuller information?
@article{Gabow85,
author = "H. N. Gabow",
title = "Scaling Algorithms for Network Problems",
journal = jcss,
year = 1985,
volume = 31,
pages = "148--168"
}
@article{GabowTa85,
author = "Harold N. Gabow and Robert E. Tarjan",
title = "A Linear-Time Algorithm for a Special Case of Disjoint Set Union",
journal = jcss,
volume = 30,
number = 2,
year = 1985,
pages = "209--221"
}
@article{GabowTa89,
author = "Harold N. Gabow and Robert E. Tarjan",
title = "Faster Scaling Algorithms for Network Problems",
journal = sicomp,
volume = 18,
number = 5,
pages = "1013--1036",
mon = oct,
year = 1989
}
@article{GalilSe83,
author = "Zvi Galil and Joel Seiferas",
title = "Time-Space-Optimal String Matching",
journal = jcss,
volume = 26,
number = 3,
year = 1983,
mon = jun,
pages = "280--294"
}
@book{GareyJo79,
author = "Michael R. Garey and David S. Johnson",
title = "Computers and Intractability: A Guide to the
Theory of {NP}-Completeness",
publisher = "W. H. Freeman",
year = 1979
}
@article{Gavril72,
author = "F\u{a}nic\u{a} Gavril",
title = "Algorithms for Minimum Coloring, Maximum Clique, Minimum
Covering by Cliques, and Maximum Independent Set of a
Chordal Graph",
journal = sicomp,
year = 1972,
mon = jun,
volume = 1,
number = 2,
pages = "180--187"
}
@book{GeorgeLi81,
author = "Alan George and Joseph W-H Liu",
title = "Computer Solution of Large Sparse Positive Definite Systems",
publisher = "Prentice-Hall",
year = 1981
}
@phdthesis{Goldberg87,
author = "Andrew V. Goldberg",
title = "Efficient Graph Algorithms for Sequential and Parallel Computers",
school = "Department of Electrical Engineering and Computer Science, MIT",
year = 1987
}
% Unreferenced
@techreport{GoldbergGrTa89,
author = "Andrew V. Goldberg and Michael D. Grigoriadis and Robert E. Tarjan",
title = "Efficiency of the Network Simplex Algorithm for the Maximum Flow Problem",
institution = "Computer Science Department, Stanford University",
year = 1989,
number = "STAN-CS-89-1248"
}
@techreport{GoldbergTaTa89,
author = "Andrew V. Goldberg and \'{E}va Tardos and Robert E. Tarjan",
title = "Network Flow Algorithms",
institution = "Computer Science Department, Stanford University",
year = 1989,
number = "STAN-CS-89-1252"
}
@article{GoldbergPl87,
author = "Andrew V. Goldberg and Serge A. Plotkin",
title = "Parallel $(\Delta + 1)$ Coloring of Constant-Degree Graphs",
journal = "Information Processing Letters",
volume = 25,
number = 4,
pages = "241--245",
mon = jun,
year = 1987
}
% To appear in JACM.
@inproceedings{GoldbergTa86,
author = "Andrew V. Goldberg and Robert E. Tarjan",
title = "A New Approach to the Maximum Flow Problem",
booktitle = stoc18,
year = 1986,
pages = "136--146"
}
% Unreferenced
@unpublished{GoldfarbHa88,
author = "D. Goldfarb and J. Hao",
title = "A Primal Simplex Algorithm That Solves the Maximum Flow
Problem in At Most $nm$ Pivots and {$O(n^2 m)$} Time",
year = 1988,
note = "Department of Industrial Engineering and Operations Research,
Columbia University"
}
@article{GoldwasserMi84,
author = "Shafi Goldwasser and Silvio Micali",
title = "Probabilistic Encryption",
journal = jcss,
volume = 28,
number = 2,
year = 1984,
mon = apr,
pages = "270--299"
}
@article{GoldwasserMiRa89,
author = "Shafi Goldwasser and Silvio Micali and Charles Rackoff",
title = "The Knowledge Complexity of Interactive Proof Systems",
journal = sicomp,
volume = 18,
number = 1,
year = 1989,
mon = feb,
pages = "186--208"
}
@article{GoldwasserMiRi88,
author = "Shafi Goldwasser and Silvio Micali and Ronald L. Rivest",
title = "A Digital Signature Scheme Secure Against Adaptive
Chosen-Message Attacks",
journal = sicomp,
volume = 17,
number = 2,
year = 1988,
mon = apr,
pages = "281--308"
}
@book{GolubVL83,
author = "Gene H. Golub and Charles F. Van Loan",
title = "Matrix Computations",
publisher = "The Johns Hopkins University Press",
year = 1983
}
@book{Gonnet84,
author = "G. H. Gonnet",
title = "Handbook of Algorithms and Data Structures",
publisher = "Addison-Wesley",
year = 1984
}
@article{Graham72,
author = "R. L. Graham",
title = "An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set",
journal = ipl,
year = 1972,
volume = 1,
pages = "132--133"
}
@article{GrahamHe85,
author = "R. L. Graham and Pavol Hell",
title = "On the History of the Minimum Spanning Tree Problem",
journal = "Annals of the History of Computing",
volume = 7,
number = 1,
year = 1985,
mon = jan,
pages = "43--57"
}
@inproceedings{GuibasSe78,
author = "Leo J. Guibas and Robert Sedgewick",
title = "A Diochromatic Framework for Balanced Trees",
booktitle = focs19,
publisher = "IEEE Computer Society",
year = 1978,
pages = "8--21"}
%=H
@article{Hajnal90,
author = "P\'{e}ter90 Hajnal",
title = "An $\Omega (n^{\frac{4}{3}})$ Lower Bound on the Randomized
Complexity of Graph Properties",
journal = "Combinatorica",
volume = 11,
number = 2,
year = 1991,
pages = "131--143"
}
% Unreferenced
@incollection{Hamilton1856,
author = "W. R. Hamilton",
title = "Letter to {J}ohn {T}. {G}raves on the Icosian, 17 {O}ctober, 1856",
booktitle = "The Mathematical Papers of Sir William Rowan Hamilton, Volume~3 (Algebra)",
publisher = "Cambridge University Press",
year = 1931,
editor = "H. Halberstam and R. E. Ingram",
pages = "612--625"
}
@book{Hamming80,
author = "R. W. Hamming",
title = "Coding and Information Theory",
publisher = "Prentice-Hall",
year = 1980
}
@book{Harary69,
author = "Frank Harary",
title = "Graph Theory",
publisher = "Addison-Wesley",
year = 1969
}
% Referenced in body. Unchecked.
@article{HartmanisSt65,
author = "J. Hartmanis and R. E. Stearns",
title = "On the Computational Complexity of Algorithms",
journal = "Transactions of the American Mathematical Society",
year = 1965,
volume = 117,
pages = "285--306"
}
@book{Harvard49,
author = "{Staff of the Computation Laboratory}",
title = "Description of a Relay Calculator",
series = "The Annals of the Computation Laboratory of Harvard University",
volume = "XXIV",
publisher = "Harvard University Press",
year = 1949
}
@book{HillPe74,
author = "Frederick J. Hill and Gerald R. Peterson",
title = "Introduction to Switching Theory and Logical Design",
publisher = "John Wiley \& Sons",
year = 1974,
edition = "Second"
}
@article{Hoare61,
author = "C. A. R. Hoare",
title = "Algorithm 63 (PARTITION) and Algorithm 65 (FIND)",
journal = cacm,
volume = 4,
number = 7,
year = 1961,
mon = jul,
pages = "321--322"
}
@article{Hoare62,
author = "C. A. R. Hoare",
title = "Quicksort",
journal = "Computer Journal",
year = 1962,
mon = apr,
volume = 5,
number = 1,
pages = "10--15"
}
@article{Hoeffding56,
author = "W. Hoeffding",
title = "On the Distribution of the Number of Successes in Independent Trials",
journal = "Annals of Mathematical Statistics",
year = 1956,
volume = 27,
pages = "713--721"}
@book{Hofri87,
author = "Micha Hofri",
title = "Probabilistic Analysis of Algorithms",
publisher = "Springer-Verlag",
year = 1987
}
@article{HopcroftKa73,
author = "John E. Hopcroft and Richard M. Karp",
title = "An $n^{5/2}$ Algorithm for Maximum Matchings in Bipartite Graphs",
journal = sicomp,
volume = 2,
number = 4,
year = 1973,
mon = dec,
pages = "225--231"
}
@article{HopcroftTa73,
author = "John E. Hopcroft and Robert E. Tarjan",
title = "Efficient Algorithms for Graph Manipulation",
journal = cacm,
year = 1973,
volume = 16,
number = 6,
pages = "372--378"
}
@article{HopcroftUl73,
workauthor = "J. E. Hopcroft and J. D. Ullman",
author = "John E. Hopcroft and Jeffrey D. Ullman",
title = "Set Merging Algorithms",
journal = sicomp,
year = 1973,
volume = 2,
number = 4,
pages = "294--303"
}
@book{HopcroftUl79,
author = "John E. Hopcroft and Jeffrey D. Ullman",
title = "Introduction to Automata Theory, Languages, and Computation",
publisher = "Addison-Wesley",
year = 1979
}
@book{HorowitzSa78,
author = "Ellis Horowitz and Sartaj Sahni",
title = "Fundamentals of Computer Algorithms",
publisher = "Computer Science Press",
year = 1978
}
@inproceedings{HuSh80,
author = "T. C. Hu and M. T. Shing",
title = "Some Theorems about Matrix Multiplication",
booktitle = focs21,
publisher = "IEEE Computer Society",
year = 1980,
pages = "28--35"
}
% Unreferenced
@article{HuSh81,
author = "T. C. Hu and M. T. Shing",
title = "An $O(n)$ Algorithm to Find a Near-Optimum Partition of a Convex Polygon",
journal = "Journal of Algorithms",
volume = 2,
number = 2,
mon = jun,
year = 1981,
pages = "122-138"
}
% breakedit
% Need full journal name
@article{Huffman52,
author = "David A. Huffman",
title = "A Method for the Construction of Minimum-Re\-dun\-dan\-cy Codes",
journal = "Proceedings of the IRE",
volume = 40,
number = 9,
year = 1952,
mon = sep,
pages = "1098--1101"
}
@book{Hwang79,
author = "Kai Hwang",
title = "Computer Arithmetic: Principles, Architecture, and Design",
publisher = "John Wiley \& Sons",
year = 1979
}
@book{HwangBr84,
author = "Kai Hwang and Fay\'e A. Briggs",
title = "Computer Architecture and Parallel Processing",
publisher = "McGraw-Hill",
year = 1984
}
@book{HwangDe89,
author = "Kai Hwang and Doug DeGroot",
title = "Parallel Processing for Supercomputers and Artificial Intelligence",
publisher = "McGraw-Hill",
year = 1989
}
%=I
@article{IbarraKi75,
author = "Oscar H. Ibarra and Chul E. Kim",
title = "Fast Approximation Algorithms for the Knapsack and
Sum of Subset Problems",
journal = jacm,
year = 1975,
volume = 22,
number = 4,
mon = oct,
pages = "463--468"
}
% Unreferenced
%% When we figure out Isaac's and Singleton's initials, fill in the
%% \index entries in the chapter notes for linear-time-sorting.
@article{IsaacSi56,
author = "E. J. Isaac and R. C. Singleton",
title = "????",
journal = jacm,
volume = 3,
number = "??",
year = 1956,
month = "??",
pages = "169--174"
}
% Unreferenced
@book{Iverson62,
author = "Kenneth E. Iverson",
title = "A Programming Language",
publisher = "Wiley",
address = "New York",
year = 1962
}
%=J
% Unreferenced
@article{Jarnik30,
author = "Jarn\'{\i}k, V.",
title = "O jist\'{e}m probl\'{e}mu minim\'{a}ln\'{\i}m",
journal = "Pr\'{a}ca Moravsk\'{e} P\u{r}\'{\i}rodov\u{e}deck\'{e} Spole\u{c}nosti",
volume = 6,
year = 1930,
pages = "57--63",
note = "In Czech."
}
@article{Jarvis73,
author = "R. A. Jarvis",
title = "On the Identification of the Convex Hull of a Finite Set of Points in the Plane",
journal = ipl,
year = 1973,
volume = 2,
pages = "18--21"
}
@article{Johnson74,
author = "D. S. Johnson",
title = "Approximation Algorithms for Combinatorial Problems",
journal = jcss,
volume = 9,
year = 1974,
pages = "256--278"
}
@article{Johnson77,
author = "Donald B. Johnson",
title = "Efficient Algorithms for Shortest Paths in Sparse Networks",
journal = jacm,
year = 1977,
pages = "1--13",
volume = 24,
number = 1,
mon = jan
}
% Unreferenced
@incollection{JohnsonPa85,
author = "D. S. Johnson and C. H. Papadimitriou",
title = "Performance Guarantees for Heuristics",
booktitle = "The Traveling Salesman Problem",
publisher = "John Wiley \& Sons",
year = 1985,
chapter = 5,
pages = "145--180"
}
@article{Jones88,
author = "Douglas W. Jones",
title = "Applications of Splay Trees to Data Compression",
journal = cacm,
year = 1988,
pages = "996--1007",
volume = 31,
number = 8,
mon = Aug
}
%=K
@article{Karmarkar84,
author = "N. Karmarkar",
title = "A New Polynomial-Time Algorithm for Linear Programming",
journal = "Combinatorica",
volume = 4,
number = 4,
year = 1984,
pages = "373--395"}
@incollection{Karp72,
author = "Richard M. Karp",
title = "Reducibility Among Combinatorial Problems",
booktitle = "Complexity of Computer Computations",
publisher = "Plenum Press",
editor = "Raymond E. Miller and James W. Thatcher",
pages = "85--103",
year = 1972
}
@article{KarpLeRiThVaVa87,
author = {R. M. Karp and F. T. Leighton and R. L. Rivest and C. D. Thompson and
U. Vazirani and V. Vazirani},
title = {Global Wire Routing in Two-Dimensional Arrays},
journal = {Algorithmica},
volume = 2,
year = 1987,
pages = {113--129}
}
@techreport{KarpRa81,
author = "Richard M. Karp and Michael O. Rabin",
title = "Efficient Randomized Pattern-Matching Algorithms",
institution = "Aiken Computation Laboratory, Harvard University",
number = "TR-31-81",
year = 1981
}
@techreport{KarpRa88,
author = "Richard M. Karp and Vijaya Ramachandran",
title = "A Survey of Parallel Algorithms for Shared-Memory Machines",
institution = "Computer Science Division (EECS), University of California, Berkeley",
number = "UCB/CSD 88/408",
mon = mar,
year = 1988
}
@article{Karzanov74,
author = "A. V. Karzanov",
title = "Determining the Maximal Flow in a Network by the Method of Preflows",
journal = "Soviet Mathematics Doklady",
year = 1974,
volume = 15,
pages = "434--437"
}
@article{Khachiyan79,
author = "L.G.Khachiyan",
title = "A Polynomial Algorithm in Linear Programming",
journal = "Soviet Mathematics Doklady",
volume = 20,
year = 1979,
pages = "191--194"
}
@article{King90,
author = "V. King",
title = "A LowerBound for the Recognition of Digraph
Properties",
journal = "Combinatorica",
volume = 10,
number = 1,
year = 1990,
pages = "53--59"}
% Changed for revision 1.2. The extra \vspace in the year entry is
% because the entry got one line shorter in revision 1.2.
@article{KirkpatrickSe86,
author = "D. G. Kirkpatrick and R. Seidel\beginrevision{1.2}",
title = "The Ultimate Planar Convex Hull Algorithm?",
journal = sicomp,
volume = 15,
number = 2,
year = "1986\endrevision{1.2}\vspace*{\baselineskip}",
pages = "287--299",
revision = "1.2"
}
@book{Knuth68I,
author = "Donald E. Knuth",
title = "{\sortby{a}}Fundamental Algorithms",
series = "The Art of Computer Programming",
publisher = "Addison-Wesley",
volume = 1,
year = 1968,
note = "Second edition, 1973."
}
@book{Knuth69II,
author = "Donald E. Knuth",
title = "{\sortby{b}}Seminumerical Algorithms",
series = "The Art of Computer Programming",
publisher = "Addison-Wesley",
year = 1969,
volume = 2,
note = "Second edition, 1981."
}
@book{Knuth73III,
author = "Donald E. Knuth",
title = "{\sortby{c}}Sorting and Searching",
series = "The Art of Computer Programming",
publisher = "Addison-Wesley",
volume = 3,
year = 1973
}
@article{Knuth76,
author = "Donald E. Knuth",
title = "Big Omicron and Big Omega and Big Theta",
journal = "ACM SIGACT News",
volume = 8,
number = 2,
year = 1976,
pages = "18--23"
}
@article{Knuth85,
author = "Donald E. Knuth",
title = "Dynamic {H}uffman Coding",
journal = "J. Algorithms",
volume = 6,
number = 2,
month = Feb,
year = 1985,
pages = "163--180"
}
@article{KnuthMoPr77,
author = "Donald E. Knuth and Morris, Jr., James H. and
Vaughan R. Pratt",
title = "Fast Pattern Matching in Strings",
journal = sicomp,
year = 1977,
mon = jun,
volume = 6,
number = 2,
pages = "323--350"
}
@book{Kohavi70,
author = "Zvi Kohavi",
title = "Switching and Finite Automata Theory",
publisher = "McGraw-Hill",
year = 1970
}
@incollection{KorteLo81,
author = "Bernhard Korte and L\'{a}szlo Lov\'{a}sz",
title = "Mathematical Structures Underlying Greedy Algorithms",
booktitle = "Fundamentals of Computation Theory",
editor = "F. Gecseg",
publisher = "Springer-Verlag",
series = "Lecture Notes in Computer Science",
year = 1981,
number = 117,
pages = "205--209"
}
@article{KorteLo83,
author = "Bernhard Korte and L\'{a}szlo Lov\'{a}sz",
title = "Structural Properties of Greedoids",
journal = "Combinatorica",
volume = 3,
year = 1983,
pages = "359--374"
}
@incollection{KorteLo84,
author = "Bernhard Korte and L\'{a}szlo Lov\'{a}sz",
title = "Greedoids---A Structural Framework for the Greedy Algorithm",
booktitle = "Progress in Combinatorial Optimization",
editor = "W. Pulleybank",
publisher = "Academic Press",
year = 1984,
pages = "221--243"
}
@article{KorteLo84b,
author = "Bernhard Korte and L\'{a}szlo Lov\'{a}sz",
title = "Greedoids and Linear Objective Functions",
journal = "SIAM Journal on Algebraic and Discrete Methods",
year = 1984,
mon = jun,
volume = 5,
number = 2,
pages = "229--238"
}
@article{Kruskal56,
author = "J. B. Kruskal",
title = "On the Shortest Spanning Subtree of a Graph and the
Traveling Salesman Problem",
year = 1956,
journal = "Proceedings of the American Mathematical Society",
volume = 7,
pages = "48--50"
}
% Check more recent publication. OK for now, but needs a number?
@techreport{Kung73,
author = "H. T. Kung",
title = "Fast Evaluation and Interpolation",
institution = "Department of Computer Science, Carnegie-Mellon University",
year = 1973,
mon = jan
}
%=L
% Unreferenced
% reference from Knuth76 and not checked
@book{Landau09,
author = {Edmund Landau},
title = {Handbuch der Lehre von der Verteilung der Primzahlen},
address = {Leipzig},
publisher = {B. G. Teubner},
year = 1909,
note = {2 volumes.}
}
@book{Lawler76,
author = "Eugene L. Lawler",
title = "Combinatorial Optimization: Networks and Matroids",
publisher = "Holt, Rinehart, and Winston",
year = 1976
}
@book{LawlerLeRiSh85,
editor = "Eugene L. Lawler and J. K. Lenstra and A. H. G. {Rinnooy Kan}
and D. B. Shmoys",
title = "The Traveling Salesman Problem",
publisher = "John Wiley \& Sons",
year = "1985"
}
@article{Lee61,
author = "C. Y. Lee",
title = "An Algorithm for Path Connection and Its Applications",
journal = "{IRE} Transactions on Electronic Computers",
volume = "EC-10",
number = 3,
mon = sep,
year = 1961,
pages = "346--365"
}
@book{Leighton90,
author = "F. Thomson Leighton",
title = "Introduction to Parallel Algorithms and Architectures:
Networks and Algorithms",
publisher = "Morgan-Kaufmann",
year = "in preparation"
}
@article{LeightonRi86,
author = {F. T. Leighton and R. L. Rivest},
title = {Estimating a Probability using Finite Memory},
journal = {IEEE Transactions on Information Theory},
year = 1986,
month = Nov,
volume = {IT-32},
number = 6,
pages = {733--742}
}
@article{LelewerHi87,
author = "Debra A. Lelewer and Daniel S. Hirschberg",
title = "Data Compression",
journal = acmcs,
volume = 19,
number = 3,
year = 1987,
mon = sep,
pages = "261--296"
}
@article{Lenstra87,
author = "Lenstra, Jr., H. W.",
title = "Factoring Integers with Elliptic Curves",
journal = "Annals of Mathematics",
volume = 126,
year = 1987,
pages = "649--673"
}
@article{Levin73,
author = "L. A. Levin",
title = "Universal Sorting Problems",
journal = "Problemy Peredachi Informatsii",
volume = 9,
number = 3,
year = 1973,
pages = "265--266",
note = "In Russian."
}
@inproceedings{Leuker78,
author = "George S. Leuker",
title = "A Data Structure for Orthogonal Range Queries",
booktitle = focs19,
publisher = "IEEE Computer Society",
year = 1978,
pages = "28--34"
}
@book{LewisPa81,
author = "Harry R. Lewis and Christos H. Papadimitriou",
title = "Elements of the Theory of Computation",
publisher = "Prentice-Hall",
year = 1981
}
@book{Liu68,
author = "C. L. Liu",
title = "Introduction to Combinatorial Mathematics",
publisher = "McGraw-Hill",
year = 1968
}
@article{Lovasz75,
author = "L\'{a}szlo Lov\'{a}sz",
title = "On the Ratio of Optimal Integral and Fractional Covers",
journal = "Discrete Mathematics",
year = 1975,
volume = 13,
pages = "383--390"
}
%=M
% Unreferenced
@article{MalhotraKuMa78,
author = "V. M. Malhotra and M. Pramodh Kumar and S. N. Maheshwari",
title = "An {$O(\card{V}^3)$} Algorithm for Finding Maximum Flows in Networks",
journal = ipl,
year = 1978,
volume = 7,
number = 6,
mon = oct,
pages = "277--278"
}
@book{Manber89,
author = "Udi Manber",
title = "Introduction to Algorithms: A Creative Approach",
publisher = "Addison-Wesley",
year = 1989
}
@article{MasekPa80,
author = "William J. Masek and Michael S. Paterson",
title = "A Faster Algorithm Computing String Edit Distances",
journal = jcss,
volume = 20,
number = 1,
mon = feb,
year = 1980,
pages = "18--31"
}
% Unreferenced
@techreport{McCreight82,
author = "Edward M. McCreight",
title = "Priority Search Trees",
institution = "Xerox Palo Alto Research Center Technical Report",
year = 1982,
number = "CSL-81-5",
month = jan
}
@book{Mehlhorn84a,
author = "Kurt Mehlhorn",
title = "{\sortby{a}}Sorting and Searching",
publisher = "Springer-Verlag",
year = 1984,
volume = 1,
series = "Data Structures and Algorithms"
}
@book{Mehlhorn84b,
author = "Kurt Mehlhorn",
title = "{\sortby{b}}Graph Algorithms and {NP}-Completeness",
publisher = "Springer-Verlag",
year = 1984,
volume = 2,
series = "Data Structures and Algorithms"
}
@book{Mehlhorn84c,
author = "Kurt Mehlhorn",
title = "{\sortby{c}}Multidimensional Searching and Computational Geometry",
publisher = "Springer-Verlag",
year = 1984,
volume = 3,
series = "Data Structures and Algorithms"
}
@incollection{MehlhornTs90,
author = {K. Mehlhorn and A. Tsakalidis},
title = {Data Structures},
booktitle = {Algorithms and Complexity},
volume = {A},
editor = {J. van Leeuwen},
year = 1990,
publisher = {Elsevier},
chapter = 6,
pages = {301--341}
}
@article{Miller76,
author = "Gary L. Miller",
title = "Riemann's Hypothesis and Tests for Primality",
journal = jcss,
year = 1976,
volume = 13,
number = 3,
mon = dec,
pages = "300--317"
}
% breakedit
@phdthesis{Monier80,
author = "Louis Monier",
title = "Algorithmes de Factorisation D'Entiers",
school = "L'U\-ni\-ver\-sit\'e Paris-Sud",
address = "Centre D'Orsay",
year = 1980,
mon = may
}
@article{Monier80b,
author = "Louis Monier",
title = "Evaluation and Comparison of Two Efficient Probabilistic
Primality Testing Algorithms",
journal = tcs,
mon = sep,
year = 1980,
volume = 12,
number = 1,
pages = "97--108"
}
@inproceedings{Moore59,
author = "Edward F. Moore",
title = "The Shortest Path Through a Maze",
booktitle = "Proceedings of the International Symposium on the Theory of Switching",
year = 1959,
pages = "285--292",
publisher = "Harvard University Press",
addr = "Cambridge, Mass.",
mon = apr
}
% Unreferenced
@inproceedings{Mulmuley88,
author = "Ketan Mulmuley",
title = "A Fast Planar Partition Algorithm, {I}",
booktitle = focs29,
publisher = "IEEE Computer Society",
year = 1988,
pages = "580--589"
}
%=N
@article{NievergeltRe73,
author = {I. Nievergelt and E. M. Reingold},
title = {Binary search trees of bounded balance},
journal = sicomp,
volume = 2,
year = 1973,
pages = {33--43}
}
@book{NivenZu80,
author = "Ivan Niven and Herbert S. Zuckerman",
title = "An Introduction to the Theory of Numbers",
publisher = "John Wiley \& Sons",
edition = "Fourth",
year = 1980
}
%=O
@article{Ofman63,
author = "Yu.\ Ofman",
title = "On the algorithmic complexity of discrete functions",
journal = "Soviet Physics Doklady",
volume = 7,
number = 7,
year = 1963,
pages = "589--591",
note = "English translation."
}
@book{OppenheimWi83,
author = "Alan V. Oppenheim and Alan S. {Willsky, with Ian T. Young}",
title = "Signals and Systems",
publisher = "Prentice-Hall",
year = 1983
}
@article{OvermarsLe82,
author = "Mark H. Overmars and Jan van Leeuwen",
title = "Dynamic Multi-Dimentional Data Structures Based on Quad- and $K-D$ Trees",
journal = "Acta Informatica",
year = 1982,
volume = 17,
pages = "267--285"
}
%=P
@book{PapadimitriouSt82,
author = "Christos H. Papadimitriou and Kenneth Steiglitz",
title = "Combinatorial Optimization: Algorithms and Complexity",
publisher = "Prentice-Hall",
year = 1982
}
@misc{Paterson74,
author = "Michael S. Paterson",
year = 1974,
note = "Unpublished lecture, Ile de Berder, France."}
@article{Pollard75,
author = "J. M. Pollard",
title = "A {Monte Carlo} Method for Factorization",
journal = "BIT",
year = 1975,
volume = 15,
pages = "331--334"
}
@article{Pomerance81,
author = "Carl Pomerance",
title = "On the Distribution of Pseudoprimes",
journal = "Mathematics of Computation",
year = 1981,
volume = 37,
number = 156,
pages = "587--593"
}
@inproceedings{Pomerance84,
author = "Carl Pomerance",
title = "The Quadratic Sieve Factoring Algorithm",
booktitle = "Advances in Cryptology",
series = "Lecture Notes in Computer Science",
publisher = "Springer-Verlag",
volume = 209,
year = 1984,
editor = "T. Beth and N. Cot and I. Ingemarrson",
pages = "169--182"
}
@proceedings{PomeranceAMS,
editor = "Carl Pomerance",
title = "Proceedings of the AMS Symposia in Applied Mathematics:
Computational Number Theory and Cryptography",
publisher = "American Mathematical Society",
year = "to appear."
}
% Unreferenced
@article{Preparata79,
author = "Franco P. Preparata",
title = "An Optimal Real Time Algorithm for Planar Convex Hulls",
journal = cacm,
volume = 22,
year = 1979,
pages = "402--405"
}
@book{PreparataSh85,
author = "Franco P. Preparata and Micheal Ian Shamos",
title = "Computational Geometry: {A}n Introduction",
publisher = "Springer-Verlag",
year = 1985
}
@book{PressFlTeVe86,
author = "William H. Press and Brian P. Flannery and
Saul A. Teukolsky and William T. Vetterling",
title = "Numerical Recipes: The Art of Scientific Computing",
publisher = "Cambridge University Press",
year = 1986
}
@book{PressFlTeVe88,
author = "William H. Press and Brian P. Flannery and
Saul A. Teukolsky and William T. Vetterling",
title = "Numerical Recipes in C",
publisher = "Cambridge University Press",
year = 1988
}
@article{Prim57,
author = "R. C. Prim",
title = "Shortest Connection Networks and Some Generalizations",
year = 1957,
journal = "Bell System Technical Journal",
volume = 36,
pages = "1389--1401"
}
@book{PurdomBr85,
workauthor = "Purdom, {Jr.,}, Paul Walton and Cynthia A. Brown",
author = "Purdom, {Jr.,}, Paul W. and Cynthia A. Brown",
title = "The Analysis of Algorithms",
publisher = "Holt, Rinehart, and Winston",
year = 1985
}
%=Q
%=R
@incollection{Rabin76,
author = "Michael O. Rabin",
title = "Probabilistic Algorithms",
booktitle = "Algorithms and Complexity: {N}ew Directions and Recent Results",
publisher = "Academic Press",
year = 1976,
editor = "J. F. Traub",
pages = "21--39"
}
@article{Rabin80,
author = "Michael O. Rabin",
title = "Probabilistic Algorithm for Testing Primality",
journal = "Journal of Number Theory",
year = 1980,
volume = 12,
pages = "128--138"
}
@article{RabinerScRa69,
author = "L. R. Rabiner and R. W. Schafer and C. M. Rader",
title = "The Chirp-$z$ Transform and Its Applications",
journal = "Bell System Technical Journal",
volume = 48,
year = 1969,
pages = "1249--1292"
}
@book{ReingoldNiDe77,
author = {Edward M. Reingold and J\"{u}rg Nievergelt and Narsingh Deo},
title = "Combinatorial Algorithms: Theory and Practice",
publisher = "Prentice-Hall",
year = 1977
}
@book{Riesel85,
author = "Hans Riesel",
title = "Prime Numbers and Computer Methods for Factorization",
publisher = {Birkh{\"{a}}user},
series = "Progress in Mathematics",
year = 1985
}
@article{Rivest87nc,
author = {Ronald L. Rivest},
title = {Network Control by {B}ayesian Broadcast},
journal = {IEEE Transactions on Information Theory},
volume = {IT-33},
number = 3,
year = 1987,
month = May,
pages = {323--340}
}
@article{RivestShAd78,
author = "Ronald L. Rivest and Adi Shamir and Leonard M. Adleman",
title = "A Method for Obtaining Digital Signatures and Public-Key
Cryptosystems",
journal = cacm,
year = 1978,
mon = feb,
volume = 21,
number = 2,
pages = "120--126",
note = "See also U.S. Patent $\mbox{4,405,829}$."
}
@article{RosenkrantzStLe77,
author = "D. J. Rosenkrantz and R. E. Stearns and P. M. Lewis",
title = "An Analysis of Several Heuristics for the Traveling Salesman
Problem",
journal = sicomp,
year = 1977,
volume = 6,
pages = "563--581"
}
@book{Rozanov69,
author = "Y. A. Rozanov",
title = "Probability Theory: A Concise Course",
publisher = "Dover",
year = 1969
}
% Unreferenced
% from Press et al.
@book{RungeKo24,
author = {C. Runge and H. K\"{o}nig},
title = "Die {G}rundlehren der Mathematischen {W}issenschaften",
volume = 11,
publisher = "Springer",
address = "Berlin",
year = 1924
}
%=S
@article{SahniGo76,
author = "S. Sahni and T. Gonzalez",
title = "{P}-Complete Approximation Problems",
journal = jacm,
year = 1976,
volume = 23,
pages = "555--565"
}
@article{Samet80,
author = "Hanan Samet",
title = "Deletion in Two-Dimentional Quad Trees",
journal = cacm,
year = 1980,
volume = 23,
number = 12,
pages = "703--710"
}
@book{Savage76,
author = "John E. Savage",
title = "The Complexity of Computing",
publisher = "John Wiley \& Sons",
year = 1976
}
@article{Sedgewick78,
author = "Robert Sedgewick",
title = "Implementing Quicksort Programs",
journal = cacm,
volume = 21,
number = 10,
year = 1978,
mon = oct,
pages = "847--857"
}
@book{Sedgewick88,
author = "Robert Sedgewick",
title = "Algorithms",
edition = "Second",
publisher = "Addison-Wesley",
year = 1988
}
% Unreferenced
@inproceedings{Shamos75,
author = "Michael Ian Shamos",
title = "Geometric Complexity",
booktitle = stoc7,
year = 1975,
pages = "224--233"
}
@inproceedings{ShamosHo75,
workauthor = "Michael Ian Shamos and Dan Hoey",
author = "Michael I. Shamos and Dan Hoey",
title = "Geometric Intersection Problems",
booktitle = focs16,
publisher = "IEEE Computer Society",
year = 1975,
pages = "208--215"
}
% Unreferenced
@phdthesis{Shamos78,
author = "Michael Ian Shamos",
title = "Computational Geometry",
school = "Department of Computer Science, Yale University",
year = 1978
}
% Unreferenced
@article{Sharir81,
author = "M. Sharir",
title = "A Strong-Connectivity Algorithm and Its Applications in
Data Flow Analysis",
journal = "Computers and Mathematics with Applications",
year = 1981,
volume = 7,
number = 1,
pages = "67--72"
}
% Unreferenced
@article{ShiloachVi82,
author = "Yossi Shiloach and Uzi Vishkin",
title = "An {$O(n^2 \log n)$} Parallel Max-Flow Algorithm",
journal = "Journal of Algorithms",
year = 1982,
volume = 3,
pages = "57--67"
}
% Unreferenced
@techreport{Sleator80,
author = "Daniel D. Sleator",
title = "An {$O(nm \log n)$} Algorithm for Maximum Network Flow",
institution = "Computer Science Department, Stanford University",
year = 1980,
number = "STAN-CS-80-831"
}
@article{SleatorTa83,
workauthor = "Daniel D. Sleator and Robert Endre Tarjan",
author = "Daniel D. Sleator and Robert E. Tarjan",
title = "A Data Structure for Dynamic Trees",
journal = jcss,
year = 1983,
volume = 26,
number = 3,
mon = jun,
pages = "362--391"
}
% Unreferenced
@inproceedings{SleatorTa84,
author = "Daniel Dominic Sleator and Robert Endre Tarjan",
title = "Amortized Efficiency of List Update Rules",
booktitle = stoc16,
year = 1984,
pages = "488--492"
}
@article{SleatorTa85,
workauthor = "Daniel Dominic Sleator and Robert Endre Tarjan",
author = "Daniel D. Sleator and Robert E. Tarjan",
title = "Self-Adjusting Binary Search Trees",
journal = jacm,
year = 1985,
volume = 32,
number = 3,
mon = jul,
pages = "652--686"
}
% Unreferenced
@article{SleatorTa86,
author = "Daniel Dominic Sleator and Robert Endre Tarjan",
title = "Self-Adjusting Heaps",
journal = sicomp,
year = 1986,
volume = 15,
number = 1,
mon = feb,
pages = "52--69"
}
@book{Spencer87,
author = "Joel Spencer",
title = "Ten Lectures on the Probabilistic Method",
publisher = "SIAM",
series = "Regional Conference Series on Applied Mathematics (No.~52)",
year = 1987
}
@book{Storer88,
author = "James A. Storer",
title = "Data Compression: Methods and Theory",
publisher = "Computer Science Press",
year = 1988
}
@book{Strang86,
author = "Gilbert Strang",
title = "Introduction to Applied Mathematics",
publisher = "Wellesley-Cambridge Press",
addr = "Wellesley, Massachusetts",
year = 1986
}
@book{Strang88,
author = "Gilbert Strang",
title = "Linear Algebra and Its Applications",
publisher = "Harcourt Brace Jovanovich",
edition = "Third",
addr = "Orlando, Florida",
year = 1988
}
@article{Strassen69,
author = "Volker Strassen",
title = "Gaussian Elimination Is Not Optimal",
journal = "Numerische Mathematik",
year = 1969,
volume = 14,
number = 3,
pages = "354--356"
}
@techreport{Szymanski75,
author = "T. G. Szymanski",
title = "A Special Case of the Maximal Common Subsequence Problem",
institution = "Computer Science Laboratory, Princeton University",
year = 1975,
number = "TR-170",
mon = jan,
addr = "Princeton, N. J."
}
%=T
@article{Tarjan72,
author = "Robert E. Tarjan",
title = "Depth First Search and Linear Graph Algorithms",
journal = sicomp,
year = 1972,
volume = 1,
number = 2,
pages = "146--160"
}
@article{Tarjan75,
author = "Robert E. Tarjan",
title = "Efficiency of a Good But Not Linear Set Union Algorithm",
journal = jacm,
volume = 22,
number = 2,
year = 1975,
pages = "215--225"
}
% breakedit
@article{Tarjan79,
author = "Robert E. Tarjan",
title = "A Class of Algorithms Which Require Nonlinear Time to Maintain Disjoint Sets",
journal = jcss,
volume = 18,
number = 2,
year = 1979,
pages = "\linebreak[4]110--127"
}
@book{Tarjan83,
workauthor = "Robert Endre Tarjan",
author = "Robert E. Tarjan",
title = "Data Structures and Network Algorithms",
publisher = "Society for Industrial and Applied Mathematics",
year = 1983
}
% Unreferenced
@article{Tarjan84,
author = "Robert Endre Tarjan",
title = "A Simple Version of {K}arzanov's Blocking Flow Algorithm",
journal = "Operations Research Letters",
year = 1984,
volume = 2,
pages = "265--268"
}
@article{Tarjan85,
workauthor = "Robert Endre Tarjan",
author = "Robert E. Tarjan",
title = "Amortized Computational Complexity",
journal = "SIAM Journal on Algebraic and Discrete Methods",
volume = 6,
number = 2,
year = 1985,
pages = "306--318"
}
@article{Tarjanva84,
author = "Robert E. Tarjan and Jan van Leeuwen",
title = "Worst-Case Analysis of Set Union Algorithms",
journal = jacm,
volume = 31,
number = 2,
year = 1984,
pages = "245--281"
}
% Unreferenced
@article{TarjanVa88,
author = "Robert E. Tarjan and Christopher J. {Van Wyck}",
title = "An {$O(n \log \log n)$}-Time Algorithm for Triangulating a Simple Polygon",
journal = sicomp,
volume = 17,
number = 1,
year = 1988,
mon = feb,
pages = "143--178"
}
@article{TarjanVi85,
author = "Robert E. Tarjan and Uzi Vishkin",
title = "An Efficient Parallel Biconnectivity Algorithm",
journal = sicomp,
volume = 14,
number = 4,
mon = nov,
year = 1985,
pages = "862--874"
}
@book{ThomasFi88,
title = "Calculus and Analytic Geometry",
author = "Thomas, {Jr.,}, George B. and Ross L. Finney",
year = 1988,
publisher = "Addison-Wesley",
edition = "Seventh"
}
%=U
%=V
@article{Valiant75,
author = "Leslie G. Valiant",
title = "Parallelism in Comparison Problems",
journal = sicomp,
volume = 4,
number = 3,
year = 1975,
pages = "348--355"
}
@inproceedings{vanEmdeBoas75,
author = "van Emde Boas, P.",
title = "Preserving Order in a Forest in Less Than Logarithmic Time",
booktitle = focs16,
publisher = "IEEE Computer Society",
year = 1975,
mon = oct,
pages = "75--84"
}
@article{Vishkin83,
author = "Uzi Vishkin",
title = "Implementation of Simultaneous Memory Address Access in
Models That Forbid It",
journal = "Journal of Algorithms",
volume = 4,
number = 1,
mon = mar,
year = 1983,
pages = "45--50"
}
@article{Vuillemin78,
author = "Jean Vuillemin",
title = "A Data Structure for Manipulating Priority Queues",
journal = cacm,
year = 1978,
mon = apr,
volume = 21,
number = 4,
pages = "309--315"
}
%=W
% Unreferenced
@article{Wagner76,
author = "Robert A. Wagner",
title = "A Shortest Path Algorithm for Edge-Sparse Graphs",
journal = jacm,
year = 1976,
volume = 23,
number = 1,
pages = "50--57",
mon = jan
}
@article{Wallace64,
author = "C. S. Wallace",
title = "A Suggestion for a Fast Multiplier",
journal = "IEEE Transactions on Electronic Computers",
volume = "EC-13",
number = 1,
mon = feb,
year = 1964,
pages = "14--17"}
@article{Warshall62,
author = "Stephen Warshall",
title = "A Theorem on Boolean Matrices",
journal = jacm,
year = 1962,
volume = 9,
number = 1,
pages = "11--12"
}
@article{WeinbergerSm56,
author = "A. Weinberger and J. L. Smith",
title = "A One-Microsecond Adder Using One-Megacycle Circuitry",
journal = "IRE Transactions on Electronic Computers",
volume = "EC-5",
number = 2,
mon = jun,
year = 1956
}
@article{Whitney35,
author = "Hassler Whitney",
title = "On the Abstract Properties of Linear Dependence",
journal = "American Journal of Mathematics",
year = 1935,
volume = 57,
pages = "509--533"
}
@book{Wilf86,
author = "Herbert S. Wilf",
title = "Algorithms and Complexity",
publisher = "Prentice-Hall",
year = 1986
}
@article{Williams64,
author = "J. W. J. Williams",
title = "Algorithm 232 (HEAPSORT)",
journal = cacm,
year = 1964,
volume = 7,
pages = "347--348"
}
@inproceedings{Winograd70,
author = "S. Winograd",
title = "On the algebraic complexity of functions",
booktitle = "Actes du Congr\`es International des Math\'ematiciens",
year = 1970,
mon = sep,
volume = 3,
pages = "283--288"
}
@phdthesis{Wyllie79,
author = "James C. Wyllie",
title = "The Complexity of Parallel Computations",
school = "Department of Computer Science, Cornell University",
year = "1979"
}
%=X
%=Y
@article{Yao81,
workauthor = "Andrew Chi-Chih Yao",
author = "Andrew C.-C. Yao",
title = "A Lower Bound to Finding Convex Hulls",
journal = jacm,
year = 1981,
volume = 28,
number = 4,
pages = "780--787"
}
% Unreferenced
@article{Yao??,
author = "F. Frances Yao",
title = "Efficient Dynamic Programming Using Quadrangle Inequalities",
journal = "unknown",
year = "??"
}
%=Z