Algorithms and Theory of Computation Handbook Second Edition General Concepts and Techniques Edited by Mikhail J. Atallah Marina Blanton Chapman & Hall/CRC Applied Algorithms and Data Structures Series Series Editor Samir Khuller University of Maryland Aims and Scopes The design and analysis of algorithms and data structures form the foundation of computer science. As current algorithms and data structures are improved and new methods are in- troduced, it becomes increasingly important to present the latest research and applications to professionals in the field. This series aims to capture new developments and applications in the design and analysis of algorithms and data structures through the publication of a broad range of textbooks, reference works, and handbooks.
We are looking for single authored works and edited compilations that will: r Appeal to students and professionals by providing introductory as well as advanced material on mathematical, statistical, and computational methods and techniques r Present researchers with the latest theories and experimentation r Supply information to interdisciplinary researchers and practitioners who use algo- rithms and data structures but may not have advanced computer science backgrounds The inclusion of concrete examples and applications is highly encouraged. The scope of the series includes, but is not limited to, titles in the areas of parallel algorithms, approxi- mation algorithms, randomized algorithms, graph algorithms, search algorithms, machine learning algorithms, medical algorithms, data structures, graph structures, tree data struc- tures, and more. We are willing to consider other relevant topics that might be proposed by potential contributors. Proposals for the series may be submitted to the series editor or directly to: Randi Cohen Acquisitions Editor Chapman & Hall/CRC Press 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487 Algorithms and Theory of Computation Handbook, Second Edition Algorithms and Theory of Computation Handbook, Second Edition: General Concepts and Techniques Algorithms and Theory of Computation Handbook, Second Edition: Special Topics and Techniques Chapman & Hall/CRC Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487-2742 © 2010 by Taylor and Francis Group, LLC Chapman & Hall/CRC is an imprint of Taylor & Francis Group, an Informa business No claim to original U.
Government works Printed in the United States of America on acid-free paper 10 9 8 7 6 5 4 3 2 1 International Standard Book Number: 978-1-58488-822-2 (Hardback) This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the valid- ity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint.
Except as permitted under U. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or uti- lized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopy- ing, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers. For permission to photocopy or use material electronically from this work, please access www.com (http:// www.com/) or contact the Copyright Clearance Center, Inc. (CCC), 222 Rosewood Drive, Danvers, MA 01923, 978-750-8400.
CCC is a not-for-profit organization that provides licenses and registration for a variety of users. For organizations that have been granted a photocopy license by the CCC, a separate system of payment has been arranged. Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe. Library of Congress Cataloging-in-Publication Data Algorithms and theory of computation handbook.
General concepts and techniques / editors, Mikhail J. Atallah and Marina Blanton. -- (Chapman & Hall/CRC applied algorithms and data structures series) Includes bibliographical references and index.1--dc22 2009017979 Visit the Taylor & Francis Web site at http://www.com and the CRC Press Web site at http://www.com Contents Preface. xiii 1 Algorithm Design and Analysis Techniques Edward M.
1-1 2 Searching Ricardo Baeza-Yates and Patricio V. 2-1 3 Sorting and Order Statistics Vladimir Estivill-Castro. 3-1 4 Basic Data Structures Roberto Tamassia and Bryan Cantrill. 4-1 5 Topics in Data Structures Giuseppe F.
Italiano and Rajeev Raman. 5-1 6 Multidimensional Data Structures for Spatial Applications Hanan Samet. 6-1 7 Basic Graph Algorithms Samir Khuller and Balaji Raghavachari. 7-1 8 Advanced Combinatorial Algorithms Samir Khuller and Balaji Raghavachari.
8-1 9 Dynamic Graph Algorithms Camil Demetrescu, David Eppstein, Zvi Galil, and Giuseppe F. 9-1 10 External-Memory Algorithms and Data Structures Lars Arge and Norbert Zeh. 10-1 11 Average Case Analysis of Algorithms Wojciech Szpankowski. 11-1 v vi Contents 12 Randomized Algorithms Rajeev Motwani and Prabhakar Raghavan.
12-1 13 Pattern Matching in Strings Maxime Crochemore and Christophe Hancart. 13-1 14 Text Data Compression Algorithms Maxime Crochemore and Thierry Lecroq. 14-1 15 General Pattern Matching Alberto Apostolico. 15-1 16 Computational Number Theory Samuel S.
16-1 17 Algebraic and Numerical Algorithms Ioannis Z. Pan, and Elias P. 17-1 18 Applications of FFT and Structured Matrices Ioannis Z. Emiris and Victor Y.
18-1 19 Basic Notions in Computational Complexity Tao Jiang, Ming Li, and Bala Ravikumar. 19-1 20 Formal Grammars and Languages Tao Jiang, Ming Li, Bala Ravikumar, and Kenneth W. 20-1 21 Computability Tao Jiang, Ming Li, Bala Ravikumar, and Kenneth W. 21-1 22 Complexity Classes Eric Allender, Michael C.
Loui, and Kenneth W. 22-1 23 Reducibility and Completeness Eric Allender, Michael C. Loui, and Kenneth W. 23-1 24 Other Complexity Classes and Measures Eric Allender, Michael C.
Loui, and Kenneth W. 24-1 25 Parameterized Algorithms Rodney G. Downey and Catherine McCartin. 25-1 26 Computational Learning Theory Sally A.
26-1 27 Algorithmic Coding Theory Atri Rudra. 27-1 Contents vii 28 Parallel Computation: Models and Complexity Issues Raymond Greenlaw and H. 28-1 29 Distributed Computing: A Glimmer of a Theory Eli Gafni. 29-1 30 Linear Programming Vijay Chandru and M.
30-1 31 Integer Programming Vijay Chandru and M. 31-1 32 Convex Optimization Florian Jarre and Stephen A. 32-1 33 Simulated Annealing Techniques Albert Y. Zomaya and Rick Kazman.
33-1 34 Approximation Algorithms for NP-Hard Optimization Problems Philip N. Klein and Neal E. I-1 Preface This handbook aims to provide a comprehensive coverage of algorithms and theoretical computer science for computer scientists, engineers, and other professionals in related scientific and engi- neering disciplines. Its focus is to provide a compendium of fundamental topics and techniques for professionals, including practicing engineers, students, and researchers.
The handbook is organized along the main subject areas of the discipline and also contains chapters from application areas that illustrate how the fundamental concepts and techniques come together to provide efficient solutions to important practical problems. The contents of each chapter were chosen in such a manner as to help the computer professional and the engineer in finding significant information on a topic of his or her interest. While the reader may not find all the specialized topics in a given chapter, nor will the coverage of each topic be exhaustive, the reader should be able to find sufficient information for initial inquiries and a number of references to the current in-depth literature. In addition to defining terminology and presenting the basic results and techniques for their respective topics, the chapters also provide a glimpse of the major research issues concerning the relevant topics.
Compared to the first edition, this edition contains 21 new chapters and therefore provides a significantly broader coverage of the field and its application areas. This, together with the updating and revision of many of the chapters from the first edition, has made it necessary to move into a two-volume format. It is a pleasure to extend our thanks to the people and organizations who made this handbook possible: first and foremost the chapter authors, whose dedication and expertise are at the core of this handbook; the universities and research laboratories with which the authors are affiliated for providing the computing and communication facilities and the intellectual environment for this project; Randi Cohen and her colleagues at Taylor & Francis for perfect organization and logistics that spared us the tedious aspects of such a project and enabled us to focus on its scholarly side; and, last but not least, our spouses and families, who provided moral support and encouragement. Mikhail Atallah Marina Blanton ix Editors Mikhail Atallah obtained his PhD from The Johns Hopkins University in 1982 and immediately thereafter joined the computer science department at Purdue University, Klest Lafayette, Indiana, where he currently holds the rank of distinguished professor of computer science.
His research inter- ests include information security, distributed computing, algorithms, and computational geometry. A fellow of both the ACM and the IEEE, Dr. Atallah has served on the editorial boards of top journals and on the program committees of top conferences and workshops. He was a keynote and invited speaker at many national and international meetings, and a speaker in the Distinguished Colloquium Series of top computer science departments on nine occasions.
In 1999, he was selected as one of the best teachers in the history of Purdue and was included in a permanent wall display of Purdue’s best teachers, past and present. Marina Blanton is an assistant professor in the computer science and engineering department at the University of Notre Dame, Notre Dame, Indiana. She holds a PhD from Purdue University. Her research interests focus on information security, privacy, and applied cryptography, and, in particular, span across areas such as privacy-preserving computation, authentication, anonymity, and key management.
Blanton has numerous publications at top venues and is actively involved in program committee work. xi Contributors Eric Allender Rodney G. Downey Department of Computer Science School of Mathematical and Rutgers University Computing Sciences Piscataway, New Jersey Victoria University Wellington, New Zealand Alberto Apostolico College of Computing Ioannis Z. Emiris Georgia Institute of Technology Department of Informatics and Atlanta, Georgia Telecommunications Lars Arge National and Kapodistrian University of Athens Department of Computer Science Athens, Greece University of Aarhus Aarhus, Denmark David Eppstein Department of Computer Science Ricardo Baeza-Yates University of California Yahoo! Research Irvine, California Spain and Vladimir Estivill-Castro Department of Computer Science Institute for Integrated and Intelligent Systems University of Chile Griffith University Santiago, Chile Meadowbrook, Queensland, Australia Bryan Cantrill Sun Microsystems, Inc.
Eli Gafni Santa Clara, California Department of Computer Science University of California Vijay Chandru Los Angeles, California National Institute of Advanced Studies Indian Institute of Science Campus Zvi Galil Bangalore, India Department of Computer Science Maxime Crochemore Tel Aviv University Department of Computer Science Tel Aviv, Israel King’s College London London, United Kingdom Sally A. Goldman and Department of Computer Science and Engineering Institut Gaspard-Monge Washington University Université Paris-Est St. Louis, Missouri Marne-la-Vallée, France Camil Demetrescu Raymond Greenlaw Department of Computer and Department of Information, Computing, Systems Science and Engineering University of Rome “La Sapienza” Armstrong Atlantic State University Rome, Italy Savannah, Georgia xiii xiv Contributors Christophe Hancart Thierry Lecroq Laboratory of Computer, Information Computer Science Department and Processing and Systems LITIS EA 4108 Faculty of Science University of Rouen University of Rouen Mont-Saint-Aignan, France Mont-Saint-Aignan, France H. James Hoover Ming Li Department of Computing Science David R.
Cheriton School of University of Alberta Computer Science Edmonton, Alberta, Canada University of Waterloo Waterloo, Ontario, Canada Giuseppe F. Italiano Dipartimento di Informatica, Sistemie Michael C.