Algorithms and Complexity

This first part presents chapters on models of computation, complexity theory, data structures, and efficient computation in many recognized sub-disciplines of Theoretical Computer Science.

List of contents

Machine Models and Simulations (P. van Emde Boas). A Catalog of Complexity Classes (D.S. Johnson). Machine-Independent Complexity Theory (J.I. Seiferas). Kolmogorov Complexity and its Applications (M. Li, P.M.B. Vitányi). Algorithms for Finding Patterns in Strings (A.V. Aho). Data Structures (K. Mehlhorn, A. Tsakalidis). Computational Geometry (F.F. Yao). Algorithmic Motion Planning in Robotics (J.T. Schwartz, M. Sharir). Average-Case Analysis of Algorithms and Data Structures (J.S. Vitter, Ph. Flajolet). Graph Algorithms (J. van Leeuwen). Algebraic Complexity Theory (V. Strassen). Algorithms in Number Theory (A.K. Lenstra, H.W. Lenstra Jr.). Cryptography (R. Rivest). The Complexity of Finite Functions (R.B. Boppana, M. Sipser). Communication Networks (N. Pippenger). VLSI Theory (Th. Lengauer). Parallel Algorithms for Shared-Memory Machines (R.M. Karp, V. Ramachandran). General Purpose Parallel Architectures (L.G. Valiant). Subject Index.

Summary

This first part presents chapters on models of computation, complexity theory, data structures, and efficient computation in many recognized sub-disciplines of Theoretical Computer Science.

Report

"...providing professionals and students with a comprehensive overview of the main results and developments in this evolving field." --L'Enseignement Mathematique

W. Kern
"...one of the most useful and needed publications in the field." --Optima

Product details

• Authors: Bozzano G Luisa, Jan van Leeuwen, LEEUWEN JAN VAN, Bozzano G Luisa, Bozzano G. Luisa, Gerard Meurant, Unknown, Author Unknown, J. van Leeuwen
• Assisted by: Jan van Leeuwen (Editor)
• Publisher: ELSEVIER SCIENCE BV
• Languages: English
• Product format: Hardback
• Released: 12.09.1990
• EAN: 9780444880710
• ISBN: 978-0-444-88071-0
• No. of pages: 1003
• Series: Handbook of Theoretical Comput; Handbook of Theoretical Computer Science; Handbook of Theoretical Comput; Handbook of Theoretical Computer Science
• Subjects: Natural sciences, medicine, IT, technology > IT, data processing > IT; Social sciences, law, business > Media, communication > Communication science; MATHEMATICS / History & Philosophy, COMPUTERS / Machine Theory, MATHEMATICS / Combinatorics, Combinatorics & graph theory, Mathematical theory of computation, Mathematical foundations, Combinatorics and graph theory