Encyclopedia of Algorithms

1. Front Matter

   Pages 1-50

   PDF

2. A

   1. Abelian Hidden Subgroup Problem

      • Michele Mosca

      Pages 1-5

   2. Abstract Voronoi Diagrams

      • Rolf Klein

      Pages 5-8

   3. Active Learning – Modern Learning Theory

      • Maria-Florina Balcan, Ruth Urner

      Pages 8-13

   4. Active Self-Assembly and Molecular Robotics with Nubots

      • Damien Woods

      Pages 13-18

   5. Adaptive Partitions

      • Ping Deng, Weili Wu, Eugene Shragowitz, Ding-Zhu Du

      Pages 18-22

   6. Additive Spanners

      • Shiri Chechik

      Pages 22-24

   7. Adwords Pricing

      • Tian-Ming Bu

      Pages 24-27

   8. Algorithm DC-Tree for \(\boldsymbol{k}\) -Servers on Trees

      • Marek Chrobak

      Pages 27-30

   9. Algorithmic Cooling

      • Tal Mor

      Pages 30-37

   10. Algorithmic Mechanism Design

       • Ron Lavi

       Pages 37-48

   11. Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network

       • Jesper Jansson, Wing-Kin Sung

       Pages 48-52

   12. All Pairs Shortest Paths in Sparse Graphs

       • Seth Pettie

       Pages 52-55

   13. All Pairs Shortest Paths via Matrix Multiplication

       • Tadao Takaoka

       Pages 55-59

   14. All-Distances Sketches

       • Edith Cohen

       Pages 59-64

   15. Alternate Parameterizations

       • Neeldhara Misra

       Pages 64-67

   16. Alternative Performance Measures in Online Algorithms

       • Alejandro López-Ortiz

       Pages 67-72

   17. Amortized Analysis on Enumeration Algorithms

       • Takeaki Uno

       Pages 72-76

   18. AMS Sketch

       • Graham Cormode

       Pages 76-78

   19. Analyzing Cache Behaviour in Multicore Architectures

       • Alejandro López-Ortiz, Alejandro Salinger

       Pages 78-82

This dynamic reference work provides solutions to vital algorithmic problems for scholars, researchers, practitioners, teachers and students in fields such as computer science, mathematics, statistics, biology, economics, financial software, and medical informatics. 

This second edition is broadly expanded, building upon the success of its former edition with more than 450 new and updated entries. These entries are designed to ensure algorithms are presented from growing areas of research such as bioinformatics, combinatorial group testing, differential privacy, enumeration algorithms, game theory, massive data algorithms, modern learning theory, social networks, and VLSI CAD algorithms.

Over 630 entries are organized alphabetically by problem, with subentries allowing for distinct solutions. Each entry includes a description of the basic algorithmic problem; the input and output specifications; key results; examples of applications; citations to key literature, open problems, experimental results, links to data sets and downloadable code.

All entries are peer-reviewed, written by leading experts in the field—and each entry contains links to a summary of the author’s research work. 

This defining reference is available in both print and online—a dynamic living work with hyperlinks to related entries, cross references citations, and a myriad other valuable URLs.

New and Updated entries include:

Algorithmic Aspects of Distributed Sensor Networks, 

Algorithms for Modern Computers 

Bioinformatics 

Certified Reconstruction and Mesh Generation 

Combinatorial Group Testing 

Compression of Text and Data Structures 

Computational Counting 

Computational Economics 

Computational Geometry 

Differential Privacy 

Enumeration Algorithms 

Exact Exponential Algorithms 

Game Theory 

Graph Drawing 

Group Testing 

Internet Algorithms 

Kernels and Compressions 

Massive Data Algorithms 

Mathematical Optimization 

Modern Learning Theory 

Social Networks 

Stable Marriage Problems, k-SAT Algorithms 

Sublinear Algorithms 

Tile Self-Assembly 

VLSI CAD Algorithms

• Algorithmica
• Algorithms
• All-pairs shortest paths
• Approximating
• Arithmetic Coding for Data Compression
• Bin Packing
• Communication Algorithms
• Decoding
• Dynamic Tree Problems
• Factoring
• Fully Dynamic Connectivity
• Local Alignment
• MRWMay2006
• Maximum
• Minimum
• Optimal
• Randomized
• Stable
• Weighted Caching

“This is a unique and beautiful encyclopedia; you start reading and cannot find a way to stop because it is so fascinating to move from one article to another with seemingly no end. The expertise of all authors guarantees high quality of most of the articles. They are easily accessible also for readers not working in the respective field and give a quick orientation.” (Klaus Meer, Mathematical Reviews, February, 2018)

• Department of Electrical Engineering and Computer Science, Northwestern University, Evanston, USA

  Ming-Yang Kao

Ming-Yang  Kao is Professor of Computer Science at the Northwestern University, Evanston. He got a B.S. in Mathematics, 1978 at the National Taiwan University, Republic of China (Taiwan) and his Ph.D. in Computer Science, 1986, at Yale University, USA.
Prof. Kao studies the design, analysis and implementation of algorithms. His work spans a broad range of applications including bioinformatics, computational finance, electronic commerce, and nanotechnology. Kao's most recent research includes work on DNA self-assembly, variants of the traveling salesman problem, and graph labeling problems.

Kao heads the EECS Computing, Algorithms & Applications Division and is the editor-in-chief of Algorithmica.

Policies and ethics