Algorithms and Theory of Computation Handbook [Atallah 1998-11-23].pdf

(16028 KB) Pobierz
ALGORITHMS
and THEORY
of COMPUTATION
HANDBOOK
Edited by
MIKHAIL J. ATALLAH
Purdue University
Library of Congress Cataloging-in-Publication Data
Algorithms and theory of computation handbook/edited by Mikhail Atallah.
p. cm.
Includes bibliographical references and index.
ISBN 0-8493-2649-4 (alk. paper)
1. Computer algorithms. 2. Computer science. 3. Computational complexity. I. Atallah, Mikhail.
QA76.9.A43 A43 1998
98-38016
511.3—dc21
CIP
This book contains information obtained from authentic and highly regarded sources. Reprinted material is quoted with
permission, and sources are indicated. A wide variety of references are listed. Reasonable efforts have been made to publish
reliable data and information, but the author and the publisher cannot assume responsibility for the validity of all materials
or for the consequences of their use.
Neither this book nor any part may be reproduced or transmitted in any form or by any means, electronic or mechanical,
including photocopying, microfilming, and recording, or by any information storage or retrieval system, without prior
permission in writing from the publisher.
All rights reserved. Authorization to photocopy items for internal or personal use, or the personal or internal use of specific
clients, may be granted by CRC Press LLC, provided that $.50 per page photocopied is paid directly to Copyright clearance
Center, 222 Rosewood Drive, Danvers, MA 01923 USA. The fee code for users of the Transactional Reporting Service is
ISBN 0-8493-2649-4/99/$0.00+$.50. The fee is subject to change without notice. For organizations that have been granted
a photocopy license by the CCC, a separate system of payment has been arranged.
The consent of CRC Press LLC does not extend to copying for general distribution, for promotion, for creating new works,
or for resale. Specific permission must be obtained in writing from CRC Press LLC for such copying.
Direct all inquiries to CRC Press LLC, 2000 N.W. Corporate Blvd., Boca Raton, Florida 33431.
Trademark Notice:
Product or corporate names may be trademarks or registered trademarks, and are used only for
identification and explanation, without intent to infringe.
Visit the CRC Press Web site at
www.crcpress.com
©1999 by CRC Press LLC
No claim to original U.S. Government works
International Standard Book Number 0-8493-2649-4
Library of Congress Card Number 98-38016
Printed in the United States of America 2 3 4 5 6 7 8 9 0
Printed on acid-free paper
Preface
The purpose of
Algorithms and Theory of Computation Handbook
is to be a comprehensive treatment of
the subject for computer scientists, engineers, and other professionals in related scientific and engineering
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 around the main
subject areas of the discipline, and also contains chapters from applications areas that illustrate how the
fundamental concepts and techniques come together to provide elegant solutions to important practical
problems.
The contents of each chapter were chosen so that the computer professional or engineer has a high
probability of finding significant information on a topic of interest. While the reader may not find in a
chapter all the specialized topics, nor will the coverage of each topic be exhaustive, the reader should be able
to obtain sufficient information for initial inquiries and a number of references to the current in-depth
literature. Each chapter contains a section on “Research Issues and Summary” where the reader is given a
summary of research issues in the subject matter of the chapter, as well as a brief summary of the chapter.
Each chapter also contains a section called “Defining Terms” that provides a list of terms and definitions
that might be useful to the reader. The last section of each chapter is called “Further Information” and
directs the reader to additional sources of information in the chapter’s subject area; these are the sources
that contain more detail than the chapter can possibly provide. As appropriate, they include information
on societies, seminars, conferences, databases, journals, etc.
It is a pleasure to extend my thanks to the people and organizations who made this handbook possible.
My sincere thanks go to the chapter authors; it has been an honor and a privilege to work with such a
dedicated and talented group. Purdue University and the universities and research laboratories with which
the authors are affiliated deserve credit for providing the computing facilities and intellectual environment
for this project. It is also a pleasure to acknowledge the support of CRC Press and its people: Bob Stern,
Jerry Papke, Nora Konopka, Jo Gilmore, Suzanne Lassandro, Susan Fox, and Dr. Clovis L. Tondo. Special
thanks are due to Bob Stern for suggesting to me this project and continuously supporting it thereafter.
Finally, my wife Karen and my children Christina and Nadia deserve credit for their generous patience
during the many weekends when I was in my office, immersed in this project.
© 1999 by CRC Press LLC
Contributors
Eric Allender
Rutgers University,
New Brunswick, New Jersey
Angel D´az
ı
IBM T.J. Watson Research Center,
Yorktown Heights, New York
Dan Halperin
Tel Aviv University,
Tel Aviv, Israel
Alberto Apostolico
Purdue University,
West Lafayette, Indiana,
and Universit` di Padova,
a
Padova, Italy
Peter Eades
The University of Newcastle,
New South Wales, Australia
Christophe Hancart
Universit´ de Rouen,
e
Mont Saint Aignan, France
Ricardo Baeza-Yates
Universidad de Chile,
Santiago, Chile
Ioannis Z. Emiris
INRIA Sophia-Antipolis,
Sophia-Antipolis, France
H. James Hoover
University of Alberta,
Edmonton, Alberta,
Canada
Guy E. Blelloch
Carnegie Mellon University,
Pittsburgh, Pennsylvania
David Eppstein
University of California,
Irvine, California
Giuseppe F. Italiano
Universit´ “Ca’ Foscari” di Venezia,
a
via Torino, Venezia Mestre, Italy
Stefan Brands
Brands Technologies,
Utrecht, The Netherlands
Vladimir Estivill-Castro
The University of Newcastle
Callaghan, Australia
Tao Jiang
McMaster University,
Hamilton, Ontario, Canada
Bryan Cantrill
Brown University,
Providence, Rhode Island
Eli Gafni
U.C.L.A.,
Los Angeles, California
Erich Kaltofen
North Carolina State University,
Raleigh, North Carolina
Vijay Chandru
Indian Institute of Science,
Bangalore, India
Zvi Galil
Columbia University,
New York, New York
David Karger
Massachusetts Institute of
Technology,
Cambridge, Massachusetts
Chris Charnes
University of Wollongong,
Wollongong, Australia
Sally A. Goldman
Washington University,
St. Louis, Missouri
Lydia Kavraki
Stanford University,
Stanford, California
Maxime Crochemore
Universit´ de Marne-la-Vall´ e,
e
e
Noisy le Grand, France
Raymond Greenlaw
Armstrong Atlantic
State University ,
Savannah, Georgia
Rick Kazman
Carnegie Mellon University,
Pittsburgh, Pennsylvania
Yvo Desmedt
University of Wisconsin –
Milwaukee,
Milwaukee, Wisconsin
Concettina Guerra
Purdue University
West Lafayette, Indiana,
and Universit` di Padova,
a
Padova, Italy
Samir Khuller
University of Maryland,
College Park, Maryland
© 1999 by CRC Press LLC

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin