Encyclopedia of Algorithms.pdf

(55949 KB) Pobierz
Encyclopedia of Algorithms
Ming-Yang Kao (Ed.)
Encyclopedia of Algorithms
With 183 Figures and 38 Tables
With 4075 References for Further Reading
123
M
ING
-Y
ANG
K
AO
Professor of Computer Science
Department of Electrical Engineering and Computer Science
McCormick School of Engineering and Applied Science
Northwestern University
Evanston, IL 60208
USA
Library of Congress Control Number: 2007933824
ISBN: 978-0-387-30162-4
This publication is available also as:
Print publication under ISBN: 978-0-387-30770-1 and
Print and electronic bundle under ISBN: 978-0-387-36061-4
© 2008 SpringerScience+Buisiness Media, LLC.
All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer
Science+Business Media, LLC., 233 Spring Street, New York, NY 10013, USA), except for brief excerpts in connection with reviews or
scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or
by similar or dissimilar methodology now known or hereafter developed is forbidden.
The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identified as such, is not to
be taken as an expression of opinion as to whether or not they are subject to proprietary rights.
springer.com
Printed on acid free paper
SPIN: 11563624 2109letex – 5 4 3 2 1 0
Preface
The
Encyclopedia of Algorithms
aims to provide the researchers, students, and practitioners of algorithmic research with
a mechanism to efficiently and accurately find the names, definitions, key results, and further readings of important
algorithmic problems.
The work covers a wide range of algorithmic areas, and each algorithmic area is covered by a collection of entries.
An encyclopedia entry is an in-depth mini-survey of an algorithmic problem and is written by an expert researcher. The
entries for an algorithmic area are compiled by an area editor to survey the representative results in that area and can
form the core materials of a course in the area.
The
Encyclopedia
does not use the format of a conventional long survey for several reasons. A conventional survey
takes a handful of individuals too much time to write and is difficult to update. An encyclopedia entry contains the
same kinds of information as in a conventional survey, but an encyclopedia entry is much shorter and is much easier
for readers to absorb and for editors to update. Furthermore, an algorithmic area is surveyed by a collection of entries
which together provide a considerable amount of up-to-date information about the area, while the writing and updating
of the entries is distributed among multiple authors to speed up the work.
This reference work will be updated on a regular basis and will evolve towards primarily an Internet-based medium
to allow timely updates and fast search. If you have feedback regarding a particular entry, please feel free to communicate
directly with the author or the area editor of that entry. If you are interested in authoring an entry, please contact
a suitable area editor. If you have suggestions on how to improve the Encyclopedia as a whole, please contact me at
kao@northwestern.edu.
The credit of the Encyclopedia goes to the area editors, the entry authors, the entry reviewers, and the project editors
at Springer, including Jennifer Evans and Jennifer Carlson.
Ming-Yang Kao
Editor-in-Chief
Table of Contents
Abelian Hidden Subgroup Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1995; Kitaev
Adaptive Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1986; Du, Pan, Shing
Adwords Pricing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2007; Bu, Deng, Qi
Algorithm DC-Tree for
k
Servers on Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1991; Chrobak, Larmore
Algorithmic Cooling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1999; Schulman, Vazirani
2002; Boykin, Mor, Roychowdhury, Vatan, Vrijen
Algorithmic Mechanism Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1999; Nisan, Ronen
Algorithms for Spanners in Weighted Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2003; Baswana, Sen
All Pairs Shortest Paths in Sparse Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2004; Pettie
All Pairs Shortest Paths via Matrix Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2002; Zwick
Alternative Performance Measures in Online Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2000; Koutsoupias, Papadimitriou
Analyzing Cache Misses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2003; Mehlhorn, Sanders
Applications of Geometric Spanner Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2002; Gudmundsson, Levcopoulos, Narasimhan, Smid
Approximate Dictionaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2002; Buhrman, Miltersen, Radhakrishnan, Venkatesh
Approximate Regular Expression Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1995; Wu, Manber, Myers
1
4
7
9
11
16
25
28
31
34
37
40
43
46

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin