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.
  
• Susanne Albers:
  Online List Update.
  
• Neal E. Young:
  Online Paging and Caching.
  
• Online Scheduling.
  
• Juan A. Garay:
  Optimal Probabilistic Synchronous Byzantine Agreement.
  
• Optimal Radius.
  
• Robert W. Irving:
  Optimal Stable Marriage.
  

P

• Dahlia Malkhi:
  P2P.
  
• Joel Ratsaby:
  PAC Learning.
  
• Lenore Cowen:
  Packet Routing.
  
• Markus Schmidt:
  Packet Switching in Multi-Queue Switches.
  
• Rob van Stee:
  Packet Switching in Single Buffer.
  
• Monika Rauch Henzinger:
  PageRank Algorithm.
  
• Rob van Stee:
  Paging.
  
• Maria J. Serna:
  Parallel Algorithms for Two Processors Precedence Constraint Scheduling.
  
• Tak Wah Lam:
  Parallel Connectivity and Minimum Spanning Trees.
  
• Henning Fernau:
  Parameterized Algorithms for Drawing Graphs.
  
• Moshe Lewenstein:
  Parameterized Matching.
  
• Stefan Szeider:
  Parameterized SAT.
  
• Pattern Matching.
  
• Peer to Peer.
  
• Bin Ma:
  Peptide De Novo Sequencing with MS/MS.
  
• Shai Shalev-Shwartz:
  Perceptron Algorithm.
  
• Jesper Jansson:
  Perfect Phylogeny (Bounded Number of States).
  
• Giuseppe Lancia:
  Perfect Phylogeny Haplotyping.
  
• Performance Analysis.
  
• Rajmohan Rajaraman:
  Performance-Driven Clustering.
  
• Jesper Jansson:
  Phylogenetic Tree Construction from a Distance Matrix.
  
• Phylogeny Reconstruction.
  
• Joachim Gudmundsson, Giri Narasimhan, Michiel H. M. Smid:
  Planar Geometric Spanners.
  
• Glencora Borradaile:
  Planarity Testing.
  
• Veli Mäkinen, Esko Ukkonen:
  Point Pattern Matching.
  
• Aries Wei Sun:
  Position Auction.
  
• Mihai Patrascu:
  Predecessor Search.
  
• George Christodoulou:
  Price of Anarchy.
  
• Artur Czumaj, Berthold Vöcking:
  Price of Anarchy for Machines Models.
  
• Sotiris E. Nikoletseas:
  Probabilistic Data Forwarding in Wireless Sensor Networks.
  
• Peter Richter, Mario Szegedy:
  Quantization of Markov Chains.
  

Q

• Ashwin Nayak:
  Quantum Algorithm for Checking Matrix Identities.
  
• Andris Ambainis:
  Quantum Algorithm for Element Distinctness.
  
• Sean Hallgren:
  Quantum Algorithm for Factoring.
  
• Peter Richter:
  Quantum Algorithm for Finding Triangles.
  
• Andris Ambainis:
  Quantum Algorithm for Search on Grids.
  
• Sean Hallgren:
  Quantum Algorithm for Solving the Pell's Equation.
  
• Alain Tapp:
  Quantum Algorithm for the Collision Problem.
  
• Pranab Sen:
  Quantum Algorithm for the Discrete Logarithm Problem.
  
• Yaoyun Shi:
  Quantum Algorithm for the Parity Problem.
  
• Sean Hallgren:
  Quantum Algorithms for Class Group of a Number Field.
  
• Zeph Landau:
  Quantum Approximation of the Jones Polynomial.
  
• Barbara M. Terhal:
  Quantum Dense Coding.
  
• Martin Rötteler:
  Quantum Error Correction.
  
• Renato Renner:
  Quantum Key Distribution.
  
• Lov K. Grover, Ben Reichardt:
  Quantum Search.
  
• Quickest Route.
  
• Dahlia Malkhi:
  Quorums.
  

R

• Ke Yi:
  R-Trees.
  
• Vicky Papadopoulou:
  Radiocoloring in Planar Graphs.
  
• Random Number Generation.
  
• Abraham Flaxman:
  Random Planted 3-SAT.
  
• Tushar Deepak Chandra:
  Randomization in Distributed Computing.
  
• Alon Itai:
  Randomized Broadcasting in Radio Networks.
  
• Pierre Leone, Sotiris E. Nikoletseas, José D. P. Rolim:
  Randomized Energy Balance Algorithms in Sensor Networks.
  
• Leszek Gasieniec:
  Randomized Gossiping in Radio Networks.
  
• Vijaya Ramachandran:
  Randomized Minimum Spanning Tree.
  
• Maria J. Serna:
  Randomized Parallel Approximations to Max Flow.
  
• Rajmohan Rajaraman:
  Randomized Rounding.
  
• Stephen R. Tate:
  Randomized Searching on Rays or the Line.
  
• Naila Rahman, Rajeev Raman:
  Rank and Select Operations on Binary Strings.
  
• Telikepalli Kavitha:
  Ranked Matching.
  
• Rate Adjustment and Allocation.
  
• Nathan Fisher, Sanjoy K. Baruah:
  Rate-Monotonic Scheduling.
  
• Real-Time Systems.
  
• Hai Zhou:
  Rectilinear Spanning Tree.
  
• Hai Zhou:
  Rectilinear Steiner Tree.
  
• Paul M. B. Vitányi:
  Registers.
  
• Chee Yong Chan, Minos N. Garofalakis, Rajeev Rastogi:
  Regular Expression Indexing.
  
• Lucian Ilie:
  Regular Expression Matching.
  
• Eyal Even-Dar:
  Reinforcement Learning.
  
• Maurice Herlihy:
  Renaming.
  
• Response Time.
  
• Reversal Distance.
  
• Rune B. Lyngsø:
  RNA Secondary Structure Boltzmann Distribution.
  
• Rune B. Lyngsø:
  RNA Secondary Structure Prediction by Minimum Free Energy.
  
• Rune B. Lyngsø:
  RNA Secondary Structure Prediction Including Pseudoknots.
  
• Rudolf Fleischer:
  Robotics.
  
• Chee-Keng Yap, Vikram Sharma:
  Robust Geometric Computation.
  
• Robustness.
  
• József Békési, Gábor Galambos:
  Routing.
  
• Leszek Gasieniec, Chang Su, Prudence W. H. Wong:
  Routing in Geometric Networks.
  
• Dominik Schultes:
  Routing in Road Networks with Transit Nodes.
  
• Runs.
  

S

• Panagiota Fatourou:
  Schedulers for Optimistic Rate Based Flow Control.
  
• Jeff Edmonds:
  Scheduling with Equipartition.
  
• Scheduling with Unknown Job Sizes.
  
• Searching.
  
• Ted Herman:
  Self-Stabilization.
  
• Paul G. Spirakis:
  Selfish Unsplittable Flows: Algorithms for Pure Equilibria.
  
• Goran Konjevod:
  Separators in Graphs.
  
• Gonzalo Navarro:
  Sequential Approximate String Matching.
  
• Peichen Pan:
  Sequential Circuit Technology Mapping.
  
• Maxime Crochemore, Thierry Lecroq:
  Sequential Exact String Matching.
  
• Maxime Crochemore, Thierry Lecroq:
  Sequential Multiple String Matching.
  
• Michel Raynal:
  Set Agreement.
  
• Michael Dom:
  Set Cover with Almost Consecutive Ones.
  
• Nikhil Bansal:
  Shortest Elapsed Time First Scheduling.
  
• Shortest Path.
  
• Riko Jacob:
  Shortest Paths Approaches for Timetable Information.
  
• Jittat Fakcharoenphol, Satish Rao:
  Shortest Paths in Planar Graphs with Negative Weight Edges.
  
• Shortest Route.
  
• Daniele Micciancio:
  Shortest Vector Problem.
  
• Jin Wook Kim, Amihood Amir, Gad M. Landau, Kunsoo Park:
  Similarity between Compressed Strings.
  
• Camil Demetrescu, Giuseppe F. Italiano:
  Single-Source Fully Dynamic Reachability.
  
• Seth Pettie:
  Single-Source Shortest Paths.
  
• Mark S. Manasse:
  Ski Rental Problem.
  
• Evangeline F. Y. Young:
  Slicing Floorplan Orientation.
  
• Eric Ruppert:
  Snapshots in Shared Memory.
  
• Sojourn Time.
  
• Chin Lung Lu:
  Sorting by Transpositions and Reversals (Approximate Ratio 1.5).
  
• Sorting of Multi-Dimensional Keys.
  
• David A. Bader:
  Sorting Signed Permutations by Reversal (Reversal Distance).
  
• Eric Tannier:
  Sorting Signed Permutations by Reversal (Reversal Sequence).
  
• Spanning Ratio.
  
• Michael Elkin:
  Sparse Graph Spanners.
  
• Shuchi Chawla:
  Sparsest Cut.
  
• Spatial Databases and Search.
  
• Kirk Pruhs:
  Speed Scaling.
  
• Danny Z. Chen:
  Sphere Packing Problem.
  
• Maxime Crochemore, Wojciech Rytter:
  Squares and Repetitions.
  
• Robert W. Irving:
  Stable Marriage.
  
• Akihisa Tamura:
  Stable Marriage and Discrete Convex Analysis.
  
• Kazuo Iwama, Shuichi Miyazaki:
  Stable Marriage with Ties and Incomplete Lists.
  
• Stable Matching.
  
• Katarína Cechlárová:
  Stable Partition Problem.
  
• Alexis C. Kaporis, Paul G. Spirakis:
  Stackelberg Games: The Price of Optimum.
  
• Statistical Data Compression.
  
• István Miklós:
  Statistical Multiple Alignment.
  
• Vitaly Feldman:
  Statistical Query Learning.
  
• Guido Schäfer:
  Steiner Forest.
  
• Yaocun Huang, Weili Wu:
  Steiner Trees.
  
• Jay Sethuraman:
  Stochastic Scheduling.
  
• Strategyproof.
  
• Stretch Factor.
  
• String.
  
• Rolf Fagerberg:
  String Sorting.
  
• Mathieu Blanchette:
  Substring Parsimony.
  
• Meng He:
  Succinct Data Structures for Parentheses Matching.
  
• Jérémy Barbay, J. Ian Munro:
  Succinct Encoding of Permutations: Applications to Text Indexing.
  
• Juha Kärkkäinen:
  Suffix Array Construction.
  
• Paolo Ferragina:
  Suffix Tree Construction in Hierarchical Memory.
  
• Jens Stoye:
  Suffix Tree Construction in RAM.
  
• Nello Cristianini, Elisa Ricci:
  Support Vector Machines.
  
• Amit Prakash, Adnan Aziz:
  Symbolic Model Checking.
  
• Michael Elkin:
  Synchronizers, Spanners.
  

T

• t-Spanners.
  
• Adam L. Buchsbaum, Raffaele Giancarlo:
  Table Compression.
  
• Paul G. Spirakis:
  Tail Bounds for Occupancy Problems.
  
• Kurt Keutzer, Kaushik Ravindran:
  Technology Mapping.
  
• Rahul Jain:
  Teleportation of Quantum States.
  
• Srinivas Aluru:
  Text Indexing.
  
• Alexis C. Kaporis, Lefteris M. Kirousis:
  Thresholds of Random k-Sat.
  
• Maurice Herlihy:
  Topology Approach in Distributed Computing.
  
• Camil Demetrescu, Giuseppe F. Italiano:
  Trade-Offs for Dynamic Graph Problems.
  
• Yoshio Okamoto:
  Traveling Sales Person with Few Inner Points.
  
• Traveling Salesperson Problem.
  
• Tree Agreement.
  
• Tree Alignment.
  
• Paolo Ferragina, S. Srinivasa Rao:
  Tree Compression and Indexing.
  
• Hans L. Bodlaender:
  Treewidth of Graphs.
  
• Triangle Finding.
  
• Trip Planner.
  
• Truthful.
  
• Truthful Auctions.
  
• Moshe Babaioff:
  Truthful Mechanisms for One-Parameter Agents.
  
• Weizhao Wang, Xiang-Yang Li, Yu Wang:
  Truthful Multicast.
  
• Truthful Multicast Routing.
  
• Edgar Ramos:
  TSP-Based Curve Reconstruction.
  
• Joong Chae Na, Paolo Ferragina, Raffaele Giancarlo, Kunsoo Park:
  Two-Dimensional Pattern Indexing.
  
• Two-Dimensional Pattern Matching with Scaling.
  
• Amihood Amir:
  Two-Dimensional Scaled Pattern Matching.
  
• Stéphane Vialette:
  Two-Interval Pattern Problems.
  
• Robert Dick:
  Two-Level Boolean Minimization.
  
• Two-Person Game.
  
• Two-Player Game.
  
• Two-Player Nash.
  
• Two-Dimensional Compressed Matching.
  

U

• Jiong Guo:
  Undirected Feedback Vertex Set.
  
• Unified Energy-Efficient Unicast and Broadcast Topology Control.
  
• University Admissions Problem.
  
• Using Visualization in the Empirical Assessment of Algorithms.
  
• Piotr Krysta, Berthold Vöcking:
  Utilitarian Mechanism Design for Single-Minded Agents.
  

V

• Valid-Utility Games.
  
• VCG.
  
• Vector Sorting.
  
• Vertex Coloring.
  
• Vertex Cover Data Reduction.
  
• Jianer Chen:
  Vertex Cover Kernelization.
  
• Vertex Cover Preprocessing.
  
• Jianer Chen:
  Vertex Cover Search Trees.
  
• Vickrey-Clarke-Groves Mechanism.
  
• Camil Demetrescu, Giuseppe F. Italiano:
  Visualization Techniques for Algorithm Engineering.
  
• Voltage Scaling.
  
• Minming Li:
  Voltage Scheduling.
  
• Voting Systems.
  

W

• Wait-Free Consensus.
  
• Wait-Free Registers.
  
• Wait-Free Renaming.
  
• Wait-Free Shared Variables.
  
• Mark Moir:
  Wait-Free Synchronization.
  
• Warehouse Location.
  
• Weighted Bipartite Matching.
  
• Weighted Caching.
  
• Yu Wang, Weizhao Wang, Xiang-Yang Li:
  Weighted Connected Dominating Set.
  
• Julián Mestre:
  Weighted Popular Matchings.
  
• Pavlos Efraimidis, Paul G. Spirakis:
  Weighted Random Sampling.
  
• Jie Gao, Li Zhang:
  Well Separated Pair Decomposition.
  
• Rolf Klein:
  Well Separated Pair Decomposition for Unit-Disk Graph.
  
• Whole Genome Assemble.
  
• Chris Chu:
  Wire Sizing.
  
• Wireless Networks.
  
• Marek Chrobak:
  Work-Function Algorithm for k Servers.