Encyclopedia of Algorithms 2008

A

• Michele Mosca:
  Abelian Hidden Subgroup Problem.
  
• Ad-Hoc Networks.
  
• Ping Deng, Weili Wu, Eugene Shragowitz:
  Adaptive Partitions.
  
• Adword Auction.
  
• Tian-Ming Bu:
  Adwords Pricing.
  
• Agreement.
  
• Marek Chrobak:
  Algorithm DC-Tree for kServers on Trees.
  
• Tal Mor:
  Algorithmic Cooling.
  
• Ron Lavi:
  Algorithmic Mechanism Design.
  
• Surender Baswana, Sandeep Sen:
  Algorithms for Spanners in Weighted Graphs.
  
• Seth Pettie:
  All Pairs Shortest Paths in Sparse Graphs.
  
• Tadao Takaoka:
  All Pairs Shortest Paths via Matrix Multiplication.
  
• Esteban Feuerstein:
  Alternative Performance Measures in Online Algorithms.
  
• Naila Rahman:
  Analyzing Cache Misses.
  
• Joachim Gudmundsson, Giri Narasimhan, Michiel H. M. Smid:
  Applications of Geometric Spanner Networks.
  
• Srinivasan Venkatesh:
  Approximate Dictionaries.
  
• Approximate Dictionary Matching.
  
• Approximate Maximum Flow Construction.
  
• Approximate Membership.
  
• Approximate Nash Equilibrium.
  
• Approximate Periodicities.
  
• Gonzalo Navarro:
  Approximate Regular Expression Matching.
  
• Approximate Repetitions.
  
• Gregory Kucherov, Dina Sokol:
  Approximate Tandem Repeats.
  
• Jittat Fakcharoenphol, Satish Rao, Kunal Talwar:
  Approximating Metric Spaces by Tree Metrics.
  
• Approximation Algorithm.
  
• Approximation Algorithm Design.
  
• Approximation Algorithms.
  
• Approximation Algorithms in Planar Graphs.
  
• Nikhil Bansal:
  Approximation Schemes for Bin Packing.
  
• Erik D. Demaine, MohammadTaghi Hajiaghayi:
  Approximation Schemes for Planar Graph Problems.
  
• Spyros C. Kontogiannis, Panagiota N. Panagopoulou, Paul G. Spirakis:
  Approximations of Bimatrix Nash Equilibria.
  
• Mao-cheng Cai, Xiaotie Deng:
  Arbitrage in Frictional Foreign Exchange Market.
  
• Paul G. Howard, Jeffrey Scott Vitter:
  Arithmetic Coding for Data Compression.
  
• Samir Khuller:
  Assignment Problem.
  
• Maurice Herlihy:
  Asynchronous Consensus Impossibility.
  
• Xavier Défago:
  Atomic Broadcast.
  
• Atomic Multicast.
  
• Atomic Network Congestion Games.
  
• Atomic Scan.
  
• Atomic Selfish Flows.
  
• Atomicity.
  
• Jyrki Kivinen:
  Attribute-Efficient Learning.
  
• Falk Hüffner:
  Automated Search Tree Generation.
  

B

• Jan Vahrenhold:
  B-trees.
  
• Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane:
  Backtracking Based k-SAT Algorithms.
  
• Paul G. Spirakis:
  Best Response Algorithms for Selfish Routing.
  
• Erik D. Demaine, MohammadTaghi Hajiaghayi:
  Bidimensionality.
  
• David S. Johnson:
  Bin Packing.
  
• Amit Prakash, Adnan Aziz:
  Binary Decision Graph.
  
• Block Edit Distance.
  
• Block-Sorting Data Compression.
  
• Boolean Formulas.
  
• Boolean Satisfiability.
  
• Paolo Ferragina, Giovanni Manzini:
  Boosting Textual Compression.
  
• Fedor V. Fomin, Dimitrios M. Thilikos:
  Branchwidth of Graphs.
  
• Andrzej Pelc:
  Broadcasting in Geometric Radio Networks.
  
• Buffering.
  
• Paolo Ferragina, Giovanni Manzini:
  Burrows-Wheeler Transform.
  
• Michael Okun:
  Byzantine Agreement.
  

C

• Rolf Fagerberg:
  Cache-Oblivious B-Tree.
  
• Rolf Fagerberg:
  Cache-Oblivious Model.
  
• Gerth Stølting Brodal:
  Cache-Oblivious Sorting.
  
• Caching.
  
• Xavier Défago:
  Causal Order, Logical Clocks, State Machine Replication.
  
• Lisa Hellerstein:
  Certificate Complexity and Exact Learning.
  
• Mansoor Alicherry, Randeep Bhatia, Li (Erran) Li:
  Channel Assignment and Routing in Multi-Radio Wireless Mesh Networks.
  
• Hannah Honghua Yang, Martin D. F. Wong:
  Circuit Partitioning: A Network-Flow-Based Balanced Min-Cut Approach.
  
• Andrew A. Kennings, Igor L. Markov:
  Circuit Placement.
  
• Hai Zhou:
  Circuit Retiming.
  
• Hai Zhou:
  Circuit Retiming: An Incremental Approach.
  
• Boaz Patt-Shamir:
  Clock Synchronization.
  
• Lusheng Wang:
  Closest String and Substring Problems.
  
• Jens Gramm:
  Closest Substring.
  
• Clustering.
  
• Noga Alon, Raphael Yuster, Uri Zwick:
  Color Coding.
  
• Ioannis Chatzigiannakis:
  Communication in Ad Hoc Mobile Networks Using Random Walks.
  
• Tian-Ming Bu:
  Competitive Auction.
  
• Xi Chen, Xiaotie Deng:
  Complexity of Bimatrix Nash Equilibria.
  
• Qizhi Fang:
  Complexity of Core.
  
• Masayuki Takeda:
  Compressed Pattern Matching.
  
• Veli Mäkinen:
  Compressed Suffix Array.
  
• Veli Mäkinen, Gonzalo Navarro:
  Compressed Text Indexing.
  
• Alistair Moffat:
  Compressing Integer Sequences and Sets.
  
• Compression.
  
• Computational Learning.
  
• Spyros C. Kontogiannis:
  Computing Pure Equilibria in the Game of Parallel Links.
  
• Gadi Taubenfeld:
  Concurrent Programming, Mutual Exclusion.
  
• Xiuzhen Cheng, Feng Wang, Ding-Zhu Du:
  Connected Dominating Set.
  
• Sotiris E. Nikoletseas:
  Connectivity and Fault-Tolerance in Random Regular Graphs.
  
• Bernadette Charron-Bost, André Schiper:
  Consensus with Partial Synchrony.
  
• Wing-Kin Sung:
  Constructing a Galled Phylogenetic Network.
  
• Coordination Ratio.
  
• Li-Sha Huang:
  CPU Time Pricing.
  
• Chih-Wei Yi:
  Critical Range for Wireless Networks.
  
• Adam Klivans:
  Cryptographic Hardness of Learning.
  
• Rasmus Pagh:
  Cuckoo Hashing.
  

D

• Yoo Ah Kim:
  Data Migration.
  
• Rolf Niedermeier:
  Data Reduction for Domination in Graphs.
  
• Decoding.
  
• Venkatesan Guruswami:
  Decoding Reed-Solomon Codes.
  
• Camil Demetrescu, Giuseppe F. Italiano:
  Decremental All-Pairs Shortest Paths.
  
• Wen-Zhan Song, Xiang-Yang Li, Weizhao Wang:
  Degree-Bounded Planar Spanner with Low Weight.
  
• Martin Fürer:
  Degree-Bounded Trees.
  
• Leszek Gasieniec:
  Deterministic Broadcasting in Radio Networks.
  
• Ricardo A. Baeza-Yates:
  Deterministic Searching on the Line.
  
• Detour.
  
• Moshe Lewenstein:
  Dictionary Matching and Indexing (Exact and with Errors).
  
• Travis Gagie, Giovanni Manzini:
  Dictionary-Based Data Compression.
  
• Dilation.
  
• Rolf Klein:
  Dilation of Geometric Networks.
  
• Costas Busch:
  Direct Routing Algorithms.
  
• Jesper Jansson:
  Directed Perfect Phylogeny (Binary Characters).
  
• Miklós Csürös:
  Distance-Based Phylogeny Reconstruction (Fast-Converging).
  
• Richard Desper, Olivier Gascuel:
  Distance-Based Phylogeny Reconstruction (Optimal Radius).
  
• Sergio Rajsbaum:
  Distributed Algorithms for Minimum Spanning Trees.
  
• Distributed Computing.
  
• Devdatt P. Dubhashi:
  Distributed Vertex Coloring.
  
• Dominating Set.
  
• Dynamic Problems.
  
• Renato Fonseca F. Werneck:
  Dynamic Trees.
  

E

• Süleyman Cenk Sahinalp:
  Edit Distance Under Block Operations.
  
• Francis Y. L. Chin, Siu-Ming Yiu:
  Efficient Methods for Multiple Sequence Alignment with Guaranteed Error Bounds.
  
• David A. Bader:
  Engineering Algorithms for Computational Biology.
  
• Christos D. Zaroliagis:
  Engineering Algorithms for Large Network Applications.
  
• Dan Halperin:
  Engineering Geometric Algorithms.
  
• Rezaul Alam Chowdhury:
  Equivalence Between Priority Queues and Sorting.
  
• Error Correction.
  
• Error-Control Codes, Reed-Muller Code.
  
• Euclidean Graphs and Trees.
  
• Artur Czumaj:
  Euclidean Traveling Salesperson Problem.
  
• Dieter Kratsch, Fedor V. Fomin, Fabrizio Grandoni:
  Exact Algorithms for Dominating Set.
  
• Edward A. Hirsch:
  Exact Algorithms for General CNF SAT.
  
• Andreas Björklund, Thore Husfeldt:
  Exact Graph Coloring Using Inclusion-Exclusion.
  
• Catherine C. McGeoch:
  Experimental Methods for Algorithm Analysis.
  
• External Memory.
  
• Jeffrey Scott Vitter:
  External Sorting and Permuting.
  
• Extremal Problems.
  

F

• Karen Aardal, Jaroslaw Byrka, Mohammad Mahdian:
  Facility Location.
  
• Rachid Guerraoui:
  Failure Detectors.
  
• Makoto Yokoo:
  False-Name-Proof Auction.
  
• Yngve Villanger:
  Fast Minimal Triangulation.
  
• Ben Reichardt:
  Fault-Tolerant Quantum Computation.
  
• File Caching and Sharing.
  
• Yoji Kajitani:
  Floorplan and Placement.
  
• Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela, Kirk Pruhs:
  Flow Time Minimization.
  
• Formal Methods.
  
• Jason Cong, Yuzheng Ding:
  FPGA Technology Mapping.
  
• George Karakostas:
  Fractional Packing and Covering Problems.
  
• Full-Text Index Construction.
  
• Giuseppe F. Italiano:
  Fully Dynamic All Pairs Shortest Paths.
  
• Valerie King:
  Fully Dynamic Connectivity.
  
• Giuseppe F. Italiano:
  Fully Dynamic Connectivity: Upper and Lower Bounds.
  
• Giuseppe F. Italiano:
  Fully Dynamic Higher Connectivity.
  
• Giuseppe F. Italiano:
  Fully Dynamic Higher Connectivity for Planar Graphs.
  
• Giuseppe F. Italiano:
  Fully Dynamic Minimum Spanning Trees.
  
• Giuseppe F. Italiano:
  Fully Dynamic Planarity Testing.
  
• Valerie King:
  Fully Dynamic Transitive Closure.
  

G

• Vijay Sundararajan:
  Gate Sizing.
  
• Li-Sha Huang:
  General Equilibrium.
  
• Julia Chuzhoy:
  Generalized Steiner Network.
  
• René A. Sitters:
  Generalized Two-Server Problem.
  
• Makoto Yokoo:
  Generalized Vickrey Auction.
  
• Aaron Zollinger:
  Geographic Routing.
  
• Geometric Computing.
  
• Rolf Klein:
  Geometric Dilation of Geometric Networks.
  
• Joachim Gudmundsson, Giri Narasimhan, Michiel H. M. Smid:
  Geometric Spanners.
  
• Debmalya Panigrahi:
  Gomory-Hu Trees.
  
• James R. Lee:
  Graph Bandwidth.
  
• Michael Langberg:
  Graph Coloring.
  
• Samir Khuller, Balaji Raghavachari:
  Graph Connectivity.
  
• Brendan D. McKay:
  Graph Isomorphism.
  
• Graphs.
  
• Feng Wang, Weili Wu:
  Greedy Approximation Algorithms.
  
• Neal E. Young:
  Greedy Set-Cover Algorithms.
  

H

• Charilaos Efthymiou, Paul G. Spirakis:
  Hamilton Cycles in Random Intersection Graphs.
  
• Vitaly Feldman:
  Hardness of Proper Learning.
  
• David A. Bader:
  High Performance Algorithm Engineering for Large-scale Problems.
  
• Hitting Set.
  
• David Manlove:
  Hospitals/Residents Problem.
  

I

• Norbert Zeh:
  I/O-model.
  
• Camil Demetrescu, Andrew V. Goldberg, David S. Johnson:
  Implementation Challenge for Shortest Paths.
  
• Lyle A. McGeoch:
  Implementation Challenge for TSP Heuristics.
  
• Eric Ruppert:
  Implementing Shared Registers in Asynchronous Message-Passing Systems.
  
• Incentive Compatible Algorithms.
  
• Xi Chen, Xiaotie Deng:
  Incentive Compatible Selection.
  
• Incremental Algorithms.
  
• Sotiris E. Nikoletseas, Christoforos Raptopoulos, Paul G. Spirakis:
  Independent Sets in Random Intersection Graphs.
  
• Wing-Kin Sung:
  Indexed Approximate String Matching.
  
• Sandra Zilles:
  Inductive Inference.
  

K

• Bettina Speckmann:
  Kinetic Data Structures.
  
• Hans Kellerer:
  Knapsack.
  

L

• Amos Beimel, Francesco Bergadano, Nader H. Bshouty, Eyal Kushilevitz, Stefano Varricchio:
  Learning Automata.
  
• Rocco A. Servedio:
  Learning Constant-Depth Circuits.
  
• Jeffrey C. Jackson:
  Learning DNF Formulas.
  
• Luca Trevisan:
  Learning Heavy Fourier Coefficients of Boolean Functions.
  
• Adi Akavia:
  Learning Significant Fourier Coefficients over Finite Abelian Groups.
  
• Peter Auer:
  Learning with Malicious Noise.
  
• Christino Tamon:
  Learning with the Aid of an Oracle.
  
• Christos D. Zaroliagis:
  LEDA: a Library of Efficient Algorithms.
  
• Yin-Yu Ye:
  Leontief Economy Equilibrium.
  
• Ronitt Rubinfeld:
  Linearity Testing/Testing Hadamard Codes.
  
• Maurice Herlihy:
  Linearizability.
  
• Atri Rudra:
  List Decoding near Capacity: Folded RS Codes.
  
• Leah Epstein:
  List Scheduling.
  
• Leah Epstein:
  Load Balancing.
  
• Stephen F. Altschul, Bruce W. Erickson, Henry Leung:
  Local Alignment (with Affine Gap Weights).
  
• Siu-Ming Yiu:
  Local Alignment (with Concave Gap Weights).
  
• Fabian Kuhn:
  Local Approximation of Covering and Packing Problems.
  
• Thomas Moscibroda:
  Local Computation in Unstructured Radio Networks.
  
• Kazuo Iwama:
  Local Search Algorithms for kSAT.
  
• Kamesh Munagala:
  Local Search for K-medians and Facility Location.
  
• Location-Based Routing.
  
• Michael Elkin:
  Low Stretch Spanning Trees.
  
• Mihai Patrascu:
  Lower Bounds for Dynamic Connectivity.
  
• Jon Feldman:
  LP Decoding.
  

M

• Qizhi Fang:
  Majority Equilibrium.
  
• Vahab S. Mirrokni:
  Market Games and Content Distribution.
  
• Alantha Newman:
  Max Cut.
  
• Frances A. Rosamond:
  Max Leaf Spanning Tree.
  
• Ramesh Hariharan:
  Maximum Agreement Subtree (of 2 Binary Trees).
  
• Teresa M. Przytycka:
  Maximum Agreement Subtree (of 3 or More Trees).
  
• Wing-Kin Sung:
  Maximum Agreement Supertree.
  
• Vincent Berry:
  Maximum Compatible Tree.
  
• Marcin Mucha:
  Maximum Matching.
  
• Ryan Williams:
  Maximum Two-Satisfiability.
  
• Kun-Mao Chao:
  Maximum-Density Segment.
  
• Kun-Mao Chao:
  Maximum-scoring Segment with Length Restrictions.
  
• Markus Bläser:
  Metric TSP.
  
• Manor Mendel:
  Metrical Task Systems.
  
• Artur Czumaj, Andrzej Lingas:
  Minimum k-Connected Geometric Networks.
  
• Robert Krauthgamer:
  Minimum Bisection.
  
• Dimitris Fotakis, Paul G. Spirakis:
  Minimum Congestion Redundant Assignments.
  
• Christoph Ambühl:
  Minimum Energy Broadcasting in Wireless Geometric Networks.
  
• Peng-Jun Wan, Xiang-Yang Li, Ophir Frieder:
  Minimum Energy Cost Broadcasting in Wireless Networks.
  
• Nikhil Bansal:
  Minimum Flow Time.
  
• Christos Levcopoulos:
  Minimum Geometric Spanning Trees.
  
• Maxim Sviridenko:
  Minimum Makespan on Unrelated Machines.
  
• Seth Pettie:
  Minimum Spanning Trees.
  
• Christos Levcopoulos:
  Minimum Weight Triangulation.
  
• V. S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy, Aravind Srinivasan:
  Minimum Weighted Completion Time.
  
• Evangelos Kranakis, Danny Krizanc:
  Mobile Agents and Exploration.
  
• MST.
  
• Multi-Hop Radio Networks, Ad Hoc Networks.
  
• Nikhil Bansal:
  Multi-level Feedback Queues.
  
• Chandra Chekuri:
  Multicommodity Flow, Well-linked Terminals and Routing Problems.
  
• Shuchi Chawla:
  Multicut.
  
• Amihood Amir:
  Multidimensional Compressed Pattern Matching.
  
• Juha Kärkkäinen, Esko Ukkonen:
  Multidimensional String Matching.
  
• Multiple String Alignment.
  
• Tian-Ming Bu:
  Multiple Unit Auctions with Budget Constraint.
  
• Vera Asodi:
  Multiplex PCR for Gap Closing (Whole-genome Assembly).
  
• Gruia Calinescu:
  Multiway Cut.
  

N

• Weizhao Wang, Xiang-Yang Li, Xiaowen Chu:
  Nash Equilibria and Dominant Strategies in Routing.
  
• Navigation.
  
• Bhaskar DasGupta, Xin He, Tao Jiang, Ming Li, John Tromp, Louxin Zhang:
  Nearest Neighbor Interchange and Related Distances.
  
• Christos D. Zaroliagis:
  Negative Cycles in Weighted Digraphs.
  
• Xi Chen, Xiaotie Deng:
  Non-approximability of Bimatrix Nash Equilibria.
  
• Wing-Kai Hon:
  Non-shared Edges.
  
• Qizhi Fang:
  Nucleolus.
  

O

• Chengwen Chris Wang:
  O(log log n)-competitive Binary Search Tree.
  
• Nikhil Bansal:
  Oblivious Routing.
  
• Sotiris E. Nikoletseas, Olivier Powell:
  Obstacle Avoidance Algorithms in Wireless Sensor Networks.
  
• Leah Epstein:
  Online Interval Coloring.
  
• Online Learning.