 <h4>ENCYCLOPEDIA OF ALGORITHMS </h4>
 <h5>Ming-Yang Kao (Ed.)</h5>
 <h6>With 183. Figures and 38. Tables
With 4075. References for Further Reading. </h6>
 <h4>TABLE OF CONTENTS</h4>
 // absolute_page_number=1
Preface 5
About the Editor 28
List of Contributors 35  
 // absolute_page_number=0
ÁËÎÊ_Ã A
* Abelian Hidden Subgroup Problem 1
* Adaptive Partitions   4
* Adwords Pricing  7
* Algorithm DC-Tree for k Servers on Trees   9
* Algorithmic Cooling  11
* Algorithmic Mechanism Design  16
* Algorithms for Spanners in Weighted Graphs  25
* All Pairs Shortest Paths in Sparse Graphs   28
* All Pairs Shortest Paths via Matrix Multiplication  31
* Alternative Performance Measures in Online Algorithms  34
* Analyzing Cache Misses   37
* Applications of Geometric Spanner Networks  40
* Approximate Dictionaries  43
* Approximate Regular Expression Matching   46
* ApproximateTandem Repeats 48
* Approximating Metric Spaces by Tree Metrics   51
* Approximations of Bimatrix Nash Equilibria   53
* ApproximationSchemes for Bin Packing   57
* ApproximationSchemes for Planar Graph Problems  59
* Arbitrage in Frictional Foreign Exchange Market  62
* ArithmeticCoding for Data Compression   65
* Assignment Problem  68
* Asynchronous Consensus Impossibility 70
* Atomic Broadcast  73
* Attribute-Efficient Learning  77
* Automated Search Tree Generation 78 
ÁËÎÊ_Ã B
* Backtracking Based k-SAT Algorithms   83
* Best Response Algorithms for Selfish Routing  86
* Bidimensionality  88
* Binary Decision Graph 90
* TableofContents  IX
* Bin Packing 94
* Boosting Textual Compression   97
* Branchwidth of Graphs 101
* Broadcasting in Geometric Radio Networks   105
* B-trees  108
* Burrows–WheelerTransform  112
* Byzantine Agreement 116    
ÁËÎÊ_Ã C
* Cache-Oblivious B-Tree   121
* Cache-Oblivious Model   123
* Cache-Oblivious Sorting   126
* Causal Order, Logical Clocks, State Machine Replication  129
* Certificate Complexity and Exact Learning  131
* Channel Assignment and Routing in Multi-Radio Wireless Mesh Networks 134
* Circuit Partitioning: A Network-Flow-Based Balanced Min-Cut Approach  138
* Circuit Placement  143
* Circuit Retiming   146
* Circuit Retiming: An Incremental Approach   149
* Clock Synchronization 152
* Closest String and Substring Problems 155
* Closest Substring  156
* Color Coding   158
* Communicationin Ad Hoc Mobile Networks Using Random Walks   161
* Competitive Auction  165
* Complexity of Bimatrix Nash Equilibria 166
* Complexity of Core 168
* Compressed Pattern Matching 171
* Compressed Suffix Array 174
* Compressed Text Indexing   176
* Compressing Integer Sequences and Sets   178
* Computing Pure Equilibria in the Game of Parallel Links  183
* Concurrent Programming, Mutual Exclusion 188
* Connected DominatingSet   191
* Connectivity and Fault-Tolerance in Random Regular Graphs 195
* Consensus with Partial Synchrony  198
* Constructing a Galled Phylogenetic Network  202
* CPU Time Pricing  205
* Critical Range for Wireless Networks  207
* Cryptographic Hardness of Learning  210
* Cuckoo Hashing   212 
ÁËÎÊ_Ã D
* Data Migration  217
* Data Reduction for Dominationin Graphs  220
* Decoding Reed–Solomon Codes   222
* Decremental All-Pairs Shortest Paths   226
* Degree-Bounded Planar Spanner with Low Weight   228
* Degree-Bounded Trees 231
* Deterministic Broadcasting in Radio Networks 233
* Deterministic Searching on the Line 235
* Dictionary-Based Data Compression 236
* Dictionary Matching and Indexing (Exact and with Errors)   240
* Dilation of Geometric Networks  244
* Directed Perfect Phylogeny (Binary Characters) 246
* Direct Routing Algorithms   248
* Distance-Based Phylogeny Reconstruction (Fast-Converging)  251
* Distance-Based Phylogeny Reconstruction (Optimal Radius) 253
* Distributed Algorithms for Minimum Spanning Trees 256
* Distributed Vertex Coloring  258
* Dynamic Trees  260
ÁËÎÊ_Ã E
* Edit Distance Under Block Operations   265
* Efficient Methods for Multiple Sequence Alignment with Guaranteed Error Bounds  267
* Engineering Algorithms for Computational Biology   270
* Engineering Algorithms for Large Network Applications  272
* Engineering GeometricAlgorithms   274
* Equivalence Between Priority Queues and Sorting 278
* Euclidean Traveling Salesperson Problem  281
* Exact Algorithms for Dominating Set 284
* Exact Algorithms for General CNF SAT   286
* Exact Graph Coloring Using Inclusion–Exclusion  289
* Experimental Methods for Algorithm Analysis  290
* External Sorting and Permuting   291
ÁËÎÊ_Ã F
* Facility Location   299
* Failure Detectors  304
* False-Name-Proof Auction   308
* Fast Minimal Triangulation   310
* Fault-Tolerant Quantum Computation  313
* Floorplan and Placement 317
* Flow Time Minimization   320
* FPGA Technology Mapping 322
* Fractional Packing and Covering Problems  326
* Fully Dynamic All Pairs Shortest Paths   329
* Fully Dynamic Connectivity 331
* Fully Dynamic Connectivity: Upper and Lower Bounds   332
* Fully Dynamic Higher Connectivity  335
* Fully Dynamic Higher Connectivity for Planar Graphs 337
* Fully Dynamic Minimum Spanning Trees   339
* Fully Dynamic Planarity Testing   342
* Fully Dynamic Transitive Closure 343 
ÁËÎÊ_Ã G
* Gate Sizing 345
* General Equilibrium  347
* Generalized Steiner Network  349
* GeneralizedTwo-Server Problem 351
* Generalized Vickrey Auction  353
* Geographic Routing  355
* Geometric Dilation of Geometric Networks  358
* Geometric Spanners  360
* Gomory–Hu Trees  364
* Graph Bandwidth  366
* Graph Coloring 368
* Graph Connectivity 371
* Graph Isomorphism   373
* Greedy Approximation Algorithms   376
* Greedy Set-Cover Algorithms   379
* 1974–1979, Chvatal, Johnson, Lovasz, Stein  
ÁËÎÊ_Ã H
* Hamilton Cycles in Random Intersection Graphs  383
* Hardness of Proper Learning  385
* High Performance Algorithm Engineering for Large-scale Problems   387
* Hospitals/Residents Problem 390
* Implementation Challenge for Shortest Paths  395
* Implementation Challenge for TSP Heuristics  398
* Implementing Shared Registers in Asynchronous Message-Passing Systems  400
* Incentive Compatible Selection  403
* Independent Sets in Random Intersection Graphs 405
* Indexed ApproximateString Matching 408
* Inductive Inference 411
* I/O-model   413 
ÁËÎÊ_Ã K
* Kinetic Data Structures 417
* Knapsack   419 
ÁËÎÊ_Ã L
* Learning with the Aid of an Oracle  423
* Learning Automata 425
* Learning Constant-Depth Circuits 429
* Learning DNF Formulas   431
* Learning Heavy Fourier Coefficients of Boolean Functions 434
* Learning with Malicious Noise   436
* Learning Significant Fourier Coefficients over Finite Abelian Groups   438
* LEDA: a Library of Efficient Algorithms 442
* Leontief Economy Equilibrium 444
* Linearity Testing/Testing Hadamard Codes   446
* Linearizability  450
* List Decoding near Capacity: Folded RS Codes   453
* List Scheduling  455
* Load Balancing 457
* Local Alignment (with Affine Gap Weights)  459
* Local Alignment (with Concave Gap Weights)  461
* Local Approximation of Covering and Packing Problems  463
* Local Computation in Unstructured Radio Networks   466
* Local Search Algorithms for kSAT 468
* Local Search for K-medians and Facility Location   470
* Lower Bounds for Dynamic Connectivity   473
* Low Stretch Spanning Trees  477
* LP Decoding   478   
ÁËÎÊ_Ã M
* Majority Equilibrium  483
* Market Games and Content Distribution   485
* Max Cut 489
* Maximum Agreement Subtree (of 2 Binary Trees)  492
* Maximum Agreement Subtree (of 3 or More Trees)  495
* Maximum Agreement Supertree 497
* Maximum Compatible Tree   499
* Maximum-Density Segment  502
* Maximum Matching   504
* Maximum-scoringSegment with Length Restrictions 506
* Maximum Two-Satisfiability  507
* Max Leaf Spanning Tree   511
* Metrical Task Systems 514
* Metric TSP   517
* Minimum Bisection 519
* Minimum Congestion Redundant Assignments 522
* Minimum Energy Broadcastingin Wireless Geometric Networks 526
* Minimum Energy Cost Broadcastingin Wireless Networks   528
* Minimum Flow Time  531
* Minimum GeometricSpanning Trees 533
* Minimum k-Connected Geometric Networks 536
* Minimum Makespan on UnrelatedMachines 539
* Minimum Spanning Trees 541
* Minimum Weighted CompletionTime   544
* Minimum Weight Triangulation  546
* Mobile Agents and Exploration  548
* Multicommodity Flow, Well-linked Terminals and Routing Problems   551
* Multicut 554
* MultidimensionalCompressed Pattern Matching  556
* Multidimensional String Matching  559
* Multi-level Feedback Queues 562
* Multiple Unit Auctions with Budget Constraint 563
* Multiplex PCR for Gap Closing (Whole-genome Assembly)   565
* Multiway Cut   567     
ÁËÎÊ_Ã N
* Nash Equilibria and Dominant Strategies in Routing  571
* Nearest Neighbor Interchange and Related Distances  573
* Negative Cycles in Weighted Digraphs  576
* Non-approximability of Bimatrix Nash Equilibria  578
* Non-shared Edges   579
* Nucleolus   581 
ÁËÎÊ_Ã O
* Oblivious Routing  585
* Obstacle Avoidance Algorithms in Wireless Sensor Networks 588
* O(log logn)-competitive Binary Search Tree   592
* Online Interval Coloring   594
* Online List Update  598
* Online Paging and Caching   601
* Optimal Probabilistic Synchronous Byzantine Agreement   604
* Optimal Stable Marriage  606
ÁËÎÊ_Ã P
* P2P  611
* Packet Routing  616
* Packet Switching in Multi-Queue Switches  618
* Packet Switching in Single Buffer 621
* PAC Learning   622
* PageRank Algorithm  624
* Paging  625
* Parallel Algorithms for Two Processors Precedence Constraint Scheduling 627
* Parallel Connectivity and Minimum Spanning Trees   629
* ParameterizedAlgorithms for Drawing Graphs 631
* ParameterizedMatching 635
* ParameterizedSAT 639
* Peptide De Novo Sequencingwith MS/MS  640
* Perceptron Algorithm 642
* Perfect Phylogeny (Bounded Number of States)   644
* Perfect Phylogeny Haplotyping  647
* Performance-Driven Clustering  650
* Phylogenetic Tree Construction from a Distance Matrix   651
* Planar Geometric Spanners 653
* Planarity Testing   656
* Point Pattern Matching   657
* Position Auction   660
* Predecessor Search 661
* Price of Anarchy   665
* Price of Anarchy for Machines Models   667
* Probabilistic Data Forwarding in Wireless Sensor Networks  671 
ÁËÎÊ_Ã Q
* Quantization of Markov Chains  677
* Quantum Algorithm for Checking Matrix Identities   680
* Quantum Algorithm for the Collision Problem  682
* Quantum Algorithm for the Discrete Logarithm Problem  683
* Quantum Algorithm for Element Distinctness  686
* Quantum Algorithm for Factoring  689
* Quantum Algorithm for Finding Triangles  690
* Quantum Algorithm for the Parity Problem   693
* Quantum Algorithms for Class Group of a Number Field  694
* Quantum Algorithm for Search on Grids   696
* Quantum Algorithm for Solving the Pell’s Equation   698
* Quantum Approximation of the Jones Polynomial  700
* Quantum Dense Coding   703
* Quantum Error Correction   705
* Quantum Key Distribution   708
* Quantum Search 712
* Quorums  715       
ÁËÎÊ_Ã R
* Radiocoloring in Planar Graphs  721
* Randomizationin Distributed Computing  723
* RandomizedBroadcastingin Radio Networks  725
* RandomizedEnergy Balance Algorithms in Sensor Networks 728
* RandomizedGossiping in Radio Networks  731
* RandomizedMinimum Spanning Tree   732
* RandomizedParallel Approximationsto Max Flow  734
* RandomizedRounding 737
* RandomizedSearching on Rays or the Line  740
* Random Planted 3-SAT 742
* Ranked Matching  744
* Rank and Select Operations on Binary Strings  748
* Rate-MonotonicScheduling  751
* Rectilinear Spanning Tree  754
* Rectilinear Steiner Tree   757
* Registers  761
* Regular Expression Indexing  764
* Regular Expression Matching   768
* Reinforcement Learning   771
* Renaming   774
* RNA Secondary Structure Boltzmann Distribution 777
* RNA Secondary Structure Prediction Including Pseudoknots 780
* RNA Secondary Structure Prediction by Minimum Free Energy  782
* Robotics 785
* Robust Geometric Computation   788
* Routing 791
* Routing in GeometricNetworks  793
* Routing in Road Networks with Transit Nodes   796
* R-Trees  800
ÁËÎÊ_Ã S
* Schedulers for Optimistic Rate Based Flow Control  803
* Scheduling with Equipartition   806
* Selfish Unsplittable Flows: Algorithms for Pure Equilibria   810
* Self-Stabilization  812
* Separators in Graphs  815
* Sequential Approximate String Matching   818
* Sequential Circuit Technology Mapping 820
* Sequential Exact String Matching 824
* Sequential Multiple String Matching  826
* Set Agreement  829
* Set Cover with Almost Consecutive Ones   832
* Shortest Elapsed Time First Scheduling 834
* Shortest Paths Approaches for Timetable Information   837
* Shortest Paths in Planar Graphs with Negative Weight Edges 838
* Shortest Vector Problem  841
* Similarity between Compressed Strings  843
* Single-Source Fully Dynamic Reachability  846
* Single-Source Shortest Paths  847
* Ski Rental Problem 849
* Slicing Floorplan Orientation 852
* Snapshots in Shared Memory   855
* Sorting Signed Permutations by Reversal (Reversal Distance) 858
* Sorting Signed Permutations by Reversal (Reversal Sequence)  860
* Sorting by Transpositions and Reversals (Approximate Ratio 1.5)   863
* Sparse Graph Spanners   867
* Sparsest Cut 868
* Speed Scaling  870
* Sphere Packing Problem  871
* Squares and Repetitions   874
* Stable Marriage   877
* Stable Marriage and Discrete Convex Analysis  880
* Stable Marriage with Ties and Incomplete Lists 883
* Stable Partition Problem 885
* Stackelberg Games: The Price of Optimum  888
* Statistical Multiple Alignment   892
* Statistical Query Learning 894
* Steiner Forest   897
* Steiner Trees   900
* Stochastic Scheduling 904
* String Sorting  907
* Substring Parsimony  910
* Succinct Data Structures for Parentheses Matching   912
* Succinct Encoding of Permutations: Applications to Text Indexing 915
* Suffix Array Construction 919
* Suffix Tree Construction in Hierarchical Memory  922
* Suffix Tree Construction in RAM   925
* Support Vector Machines 928
* Symbolic Model Checking  932
* Synchronizers, Spanners 935
ÁËÎÊ_Ã T
* Table Compression 939
* Tail Bounds for Occupancy Problems 942
* Technology Mapping   944
* Teleportation of Quantum States 947
* Text Indexing 950
* Thresholds of Random k-Sat  954
* Topology Approach in Distributed Computing 956
* Trade-Offs for Dynamic Graph Problems   958
* Traveling Sales Person with Few Inner Points  961
* Tree Compression and Indexing   964
* Treewidth of Graphs  968
* Truthful Mechanisms for One-Parameter Agents  970
* Truthful Multicast  973
* TSP-Based Curve Reconstruction 976
* Two-DimensionalPattern Indexing   979
* Two-DimensionalScaledPattern Matching 982
* Two-Interval Pattern Problems  985
* Two-Level Boolean Minimization 989
ÁËÎÊ_Ã U
* UndirectedFeedback Vertex Set 995
* Utilitarian Mechanism Design for Single-Minded Agents  997 
ÁËÎÊ_Ã V
* Vertex Cover Kernelization   1003
* Vertex Cover Search Trees   1006
* Visualization Techniques for Algorithm Engineering 1008
* Voltage Scheduling 1011 
ÁËÎÊ_Ã W
* Wait-Free Synchronization   1015
* Weighted Connected DominatingSet   1020
* Weighted Popular Matchings   1023
* Weighted Random Sampling  1024
* Well Separated Pair Decomposition 1027
* Well Separated Pair Decomposition for Unit–Disk Graph  1030
* Wire Sizing 1032
* Work-Function Algorithm for k Servers 1035
// @
Chronological Index 1039
Bibliography 1053
Index 1157