biblio.htm

CLRS-算法导论

<a name="0a29_0043">[66] William Feller. <I>An Introduction to Probability Theory and Its Applications</I>. John Wiley &amp; Sons, third edition, 1968.<a name="0a29_0043"><P>
<a name="0a29_0044">[67] M. J. Fischer and A. R. Meyer. Boolean matrix multiplication and transitive closure. In <I>Proceedings of the Twelfth Annual Symposium on Switching and Automata Theory</I>, pages 129-131. IEEE Computer Society, 1971.<a name="0a29_0044"><P>
<a name="0a29_0045">[68] Robert W. Floyd. Algorithm 97 (SHORTEST PATH). <I>Communications of the ACM</I>, 5(6):345, 1962.<a name="0a29_0045"><P>
<a name="0a29_0046">[69] Robert W. Floyd. Algorithm 245 (TREESORT). <I>Communications of the ACM</I>, 7:701, 1964.<a name="0a29_0046"><P>
<a name="0a29_0047">[70] Robert W. Floyd and Ronald L. Rivest. Expected time bounds for selection. <I>Communications of the ACM</I>, 18(3):165-172, 1975.<a name="0a29_0047"><P>
<a name="0a29_0048">[71] Lestor R. Ford, Jr., and D. R. Fulkerson. <I>Flows in Networks</I>. Princeton University Press, 1962.<a name="0a29_0048"><P>
<a name="0a29_0049">[72] Lestor R. Ford, Jr., and Selmer M. Johnson. A tournament problem. <I>The American Mathematical Monthly</I>, 66:387-389, 1959.<a name="0a29_0049"><P>
<a name="0a29_004a">[73] Steven Fortune and James Wyllie. Parallelism in random access machines. In <I>Proceedings of the Tenth Annual ACM Symposium on Theory of Computing</I>, pages 114-118, 1978.<a name="0a29_004a"><P>
<a name="0a29_004b">[74] Michael L. Fredman and Michael E. Saks. The cell probe complexity of dynamic data structures. In <I>Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing</I>, 1989.<a name="0a29_004b"><P>
<a name="0a29_004c">[75] Michael L. Fredman and Robert E. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. <I>Journal of the ACM</I>, 34(3):596-615, 1987.<a name="0a29_004c"><P>
<a name="0a29_004d">[76] Harold N. Gabow and Robert E. Tarjan. A linear-time algorithm for a special case of disjoint set union. <I>Journal of Computer and System Sciences</I>, 30(2):209-221, 1985.<a name="0a29_004d"><P>
<a name="0a29_004e">[77] Harold N. Gabow and Robert E. Tarjan. Faster scaling algorithms for network problems. <I>SIAM Journal on Computing</I>, 18(5):1013-1036, 1989.<a name="0a29_004e"><P>
<a name="0a29_004f">[78] Zvi Galil and Joel Seiferas. Time-space-optimal string matching. <I>Journal of Computer and System Sciences</I>, 26(3):280-294, 1983.<a name="0a29_004f"><P>
<a name="0a29_0050">[79] Michael R. Garey and David S. Johnson. <I>Computers and Intractability: A Guide to the Theory of NP-Completeness</I>. W. H. Freeman, 1979.<a name="0a29_0050"><P>
<a name="0a29_0051">[80] <img src="991_a.gif"> Gavril. Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. <I>SIAM Journal on Computing</I>, 1(2):180-187, 1972.<a name="0a29_0051"><P>
<a name="0a29_0052">[81] Alan George and Joseph W-H Liu. <I>Computer Solution of Large Sparse Positive Definite Systems</I>. Prentice-Hall, 1981.<a name="0a29_0052"><P>
<a name="0a29_0053">[82] Andrew V. Goldberg. <I>Efficient Graph Algorithms for Sequential and Parallel Computers</I>. PhD thesis, Department of Electrical Engineering and Computer Science, MIT, 1987.<a name="0a29_0053"><P>
<a name="0a29_0054">[83] Andrew V. Goldberg, ...va Tardos, and Robert E. Tarjan. Network flow algorithms. Technical Report STAN-CS-89-1252, Computer Science Department, Stanford University, 1989.<a name="0a29_0054"><P>
<a name="0a29_0055">[84] Andrew V. Goldberg and Serge A. Plotkin. Parallel (<img src="../images/delta12.gif"> + 1) coloring of constant-degree graphs. <I>Information Processing Letters</I>, 25(4):241-245, 1987.<a name="0a29_0055"><P>
<a name="0a29_0056">[85] Andrew V. Goldberg and Robert E. Tarjan. A new approach to the maximum flow problem. In <I>Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing</I>, pages 136-146, 1986.<a name="0a29_0056"><P>
<a name="0a29_0057">[86] Shafi Goldwasser and Silvio Micali. Probabilistic encryption. <I>Journal of Computer and System Sciences</I>, 28(2):270-299, 1984.<a name="0a29_0057"><P>
<a name="0a29_0058">[87] Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof systems. <I>SIAM Journal on Computing</I>, 18(1):186-208, 1989.<a name="0a29_0058"><P>
<a name="0a29_0059">[88] Shafi Goldwasser, Silvio Micali, and Ronald L. Rivest. A digital signature scheme secure against adaptive chosen-message attacks. <I>SIAM Journal on Computing</I>, 17(2):281-308, 1988.<a name="0a29_0059"><P>
<a name="0a29_005a">[89] Gene H. Golub and Charles F. Van Loan. <I>Matrix Computations</I>. The Johns Hopkins University Press, 1983.<a name="0a29_005a"><P>
<a name="0a29_005b">[90] G. H. Gonnet. <I>Handbook of Algorithms and Data Structures</I>. Addison-Wesley, 1984.<a name="0a29_005b"><P>
<a name="0a29_005c">[91] R. L. Graham. An efficient algorithm for determining the convex hull of a finite planar set. <I>Information Processing Letters</I>, 1:132-133, 1972.<a name="0a29_005c"><P>
<a name="0a29_005d">[92] R. L. Graham and Pavol Hell. On the history of the minimum spanning tree problem. <I>Annals of the History of Computing</I>, 7(1):43-57, 1985.<a name="0a29_005d"><P>
<a name="0a29_005e">[93] Leo J. Guibas and Robert Sedgewick. A diochromatic framework for balanced trees. In <I>Proceedings of the 19th Annual Symposium on Foundations of Computer Science</I>, pages 8-21. IEEE Computer Society, 1978.<a name="0a29_005e"><P>
<a name="0a29_005f">[94] Frank Harary. <I>Graph Theory</I>. Addison-Wesley, 1969.<a name="0a29_005f"><P>
<a name="0a29_0060">[95] J. Hartmanis and R. E. Stearns. On the computational complexity of algorithms. <I>Transactions of the American Mathematical Society</I>, 117:285-306, 1965.<a name="0a29_0060"><P>
<a name="0a29_0061">[96] Frederick J. Hill and Gerald R. Peterson. <I>Introduction to Switching Theory and Logical Design</I>. John Wiley &amp; Sons, second edition, 1974.<a name="0a29_0061"><P>
<a name="0a29_0062">[97] C. A. R. Hoare. Algorithm 63 (partition) and algorithm 65 (find). <I>Communications of the ACM</I>, 4(7):321-322, 1961.<a name="0a29_0062"><P>
<a name="0a29_0063">[98] C. A. R. Hoare. Quicksort. <I>Computer Journal</I>, 5(1):10-15, 1962.<a name="0a29_0063"><P>
<a name="0a29_0064">[99] W. Hoeffding. On the distribution of the number of successes in independent trials. <I>Annals of Mathematical Statistics</I>, 27:713-721, 1956.<a name="0a29_0064"><P>
<a name="0a29_0065">[100] Micha Hofri. <I>Probabilistic Analysis of Algorithms</I>. Springer-Verlag, 1987.<a name="0a29_0065"><P>
<a name="0a29_0066">[101] John E. Hopcroft and Richard M. Karp. An <I>n</I><SUP>5/2</SUP> algorithm for maximum matchings in bipartite graphs. <I>SIAM Journal on Computing</I>, 2(4):225-231, 1973.<a name="0a29_0066"><P>
<a name="0a29_0067">[102] John E. Hopcroft and Robert E. Tarjan. Efficient algorithms for graph manipulation. <I>Communications of the ACM</I>, 16(6):372-378, 1973.<a name="0a29_0067"><P>
<a name="0a29_0068">[103] John E. Hopcroft and Jeffrey D. Ullman. Set merging algorithms. <I>SIAM Journal on Computing</I>, 2(4):294-303, 1973.<a name="0a29_0068"><P>
<a name="0a29_0069">[104] John E. Hopcroft and Jeffrey D. Ullman.<I> Introduction to Automata Theory, Languages, and Computation</I>. Addison-Wesley, 1979.<a name="0a29_0069"><P>
<a name="0a29_006a">[105] Ellis Horowitz and Sartaj Sahni. <I>Fundamentals of Computer Algorithms</I>. Computer Science Press, 1978.<a name="0a29_006a"><P>
<a name="0a29_006b">[106] T. C. Hu and M. T. Shing. Some theorems about matrix multiplication. In <I>Proceedings of the 21st Annual Symposium on Foundations of Computer Science</I>, pages 28-35. IEEE Computer Society, 1980.<a name="0a29_006b"><P>
<a name="0a29_006c">[107] David A. Huffman. A method for the construction of minimum-redundancy codes. <I>Proceedings of the IRE</I>, 40(9):1098-1101, 1952.<a name="0a29_006c"><P>
<a name="0a29_006d">[108] Kai Hwang. <I>Computer Arithmetic: Principles, Architecture, and Design</I>. John Wiley &amp; Sons, 1979.<a name="0a29_006d"><P>
<a name="0a29_006e">[109] Kai Hwang and Fay&eacute; A. Briggs. <I>Computer Architecture and Parallel Processing</I>. McGraw-Hill, 1984.<a name="0a29_006e"><P>
<a name="0a29_006f">[110] Kai Hwang and Doug DeGroot. <I>Parallel Processing for Supercomputers and Artificial Intelligence</I>. McGraw-Hill, 1989.<a name="0a29_006f"><P>
<a name="0a29_0070">[111] Oscar H. Ibarra and Chul E. Kim. Fast approximation algorithms for the knapsack and sum of subset problems. <I>Journal of the ACM</I>, 22(4):463-468, 1975.<a name="0a29_0070"><P>
<a name="0a29_0071">[112] R. A. Jarvis. On the identification of the convex hull of a finite set of points in the plane. <I>Information Processing Letters</I>, 2:18-21, 1973.<a name="0a29_0071"><P>
<a name="0a29_0072">[113] D. S. Johnson. Approximation algorithms for combinatorial problems. <I>Journal of Computer and System Sciences</I>, 9:256-278, 1974.<a name="0a29_0072"><P>
<a name="0a29_0073">[114] Donald B. Johnson. Efficient algorithms for shortest paths in sparse networks. <I>Journal of the ACM</I>, 24(1):1-13, 1977.<a name="0a29_0073"><P>
<a name="0a29_0074">[115] N. Karmarkar. A new polynomial-time algorithm for linear programming. <I>Combinatorica</I>, 4(4):373-395, 1984.<a name="0a29_0074"><P>
<a name="0a29_0075">[116] Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller and James W. Thatcher, editors, <I>Complexity of Computer Computations</I>, pages 85-103. Plenum Press, 1972.<a name="0a29_0075"><P>
<a name="0a29_0076">[117] Richard M. Karp and Michael O. Rabin. Efficient randomized pattern-matching algorithms. Technical Report TR-31-81, Aiken Computation Laboratory, Harvard University, 1981.<a name="0a29_0076"><P>
<a name="0a29_0077">[118] Richard M. Karp and Vijaya Ramachandran. A survey of parallel algorithms for shared-memory machines. Technical Report UCB/CSD 88/408, Computer Science Division (EECS), University of California, Berkeley, 1988.<a name="0a29_0077"><P>
<a name="0a29_0078">[119] A. V. Karzanov. Determining the maximal flow in a network by the method of preflows. <I>Soviet Mathematics Doklady</I>, 15:434-437, 1974.<a name="0a29_0078"><P>
<a name="0a29_0079">[120] D. G. Kirkpatrick and R. Seidel. The ultimate planar convex hull algorithm? <I>SIAM Journal on Computing</I>, 15(2):287-299, 1986.<a name="0a29_0079"><P>
<a name="0a29_2616"><a name="0a29_007a">[121] Donald E. Knuth. <I>Fundamental Algorithms, </I>volume 1 of <I>The Art of Computer Programming</I>. Addison-Wesley, 1968. Second edition, 1973.<a name="0a29_007a"><P>
<a name="0a29_007b">[122] Donald E. Knuth. <I>Seminumerical Algorithms</I>, volume 2 of <I>The Art of Computer Programming</I>. Addison-Wesley, 1969. Second edition, 1981.<a name="0a29_007b"><P>
<a name="0a29_007c">[123] Donald E. Knuth. <I>Sorting and Searching, </I>volume 3<I> of The Art of Computer Programming</I>. Addison-Wesley, 1973.<a name="0a29_007c"><P>
<a name="0a29_007d">[124] Donald E. Knuth. Big omicron and big omega and big theta. <I>ACM SIGACT News</I>, 8(2):18-23, 1976.<a name="0a29_007d"><P>
<a name="0a29_007e">[125] Donald E. Knuth, James H. Morris, Jr., and Vaughan R. Pratt. Fast pattern matching in strings. <I>SIAM Journal on Computing</I>, 6(2):323-350, 1977.<a name="0a29_007e"><P>
<a name="0a29_007f">[126] Zvi Kohavi. <I>Switching and Finite Automata Theory</I>. McGraw-Hill, 1970.<a name="0a29_007f"><P>
<a name="0a29_2611"><a name="0a29_0080">[127] Bernhard Korte and L&aacute;szlo Lov&aacute;sz. Mathematical structures underlying greedy algorithms. In F. Gecseg, editor, <I>Fundamentals of Computation Theory</I>, number 117 in Lecture Notes in Computer Science, pages 205-209. Springer-Verlag, 1981.<a name="0a29_0080"><P>
<a name="0a29_2612"><a name="0a29_0081">[128] Bernhard Korte and L&aacute;szlo Lov&aacute;sz. Structural properties of greedoids. <I>Combinatorica</I>, 3:359-374, 1983.<a name="0a29_0081"><P>
<a name="0a29_2613"><a name="0a29_0082">[129] Bernhard Korte and L&aacute;szlo Lov&aacute;sz. Greedoids--a structural framework for the greedy algorithm. In W. Pulleybank, editor, <I>Progress in Combinatorial Optimization</I>, pages 221-243. Academic Press, 1984.<a name="0a29_0082"><P>
<a name="0a29_2614"><a name="0a29_0083">[130] Bernhard Korte and L&aacute;szlo Lov&aacute;sz. Greedoids and linear objective functions. <I>SIAM Journal on Algebraic and Discrete Methods</I>, 5(2):229-238, 1984.<a name="0a29_0083"><P>
<a name="0a29_0084">[131] J. B. Kruskal. On the shortest spanning subtree of a graph and the traveling salesman problem. <I>Proceedings of the American Mathematical Society</I>, 7:48-50, 1956.<a name="0a29_0084"><P>
<a name="0a29_0085">[132] Eugene L. Lawler. <I>Combinatorial Optimization: Networks and Matroids</I>. Holt, Rinehart, and Winston, 1976.<a name="0a29_0085"><P>
<a name="0a29_0086">[133] Eugene L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, editors. <I>The Traveling Salesman Problem</I>. John Wiley &amp; Sons, 1985.<a name="0a29_0086"><P>
<a name="0a29_0087">[134] C. Y. Lee. An algorithm for path connection and its applications. <I>IRE Transactions on Electronic Computers</I>, EC-10(3):346-365, 1961.<a name="0a29_0087"><P>
<a name="0a29_0088">[135] F. Thomson Leighton. <I>Introduction to Parallel Algorithms and Architectures: Networks and Algorithms</I>. Morgan-Kaufmann, in preparation.<a name="0a29_0088"><P>
<a name="0a29_0089">[136] Debra A. Lelewer and Daniel S. Hirschberg. Data compression. <I>ACM Computing Surveys</I>, 19(3):261-296, 1987.<a name="0a29_0089"><P>
<a name="0a29_008a">[137] H. W. Lenstra, Jr. Factoring integers with elliptic curves. <I>Annals of Mathematics</I>, 126:649-673, 1987.<a name="0a29_008a"><P>
<a name="0a29_008b">[138] L. A. Levin. Universal sorting problems. <I>Problemy Peredachi Informatsii</I>, 9(3):265-266, 1973. In Russian.<a name="0a29_008b"><P>
<a name="0a29_008c">[139] Harry R. Lewis and Christos H. Papadimitriou. <I>Elements of the Theory of Computation</I>. Prentice-Hall, 1981.<a name="0a29_008c"><P>