Front Cover.

Half Title Page.

Title Page.

Copyright Page.

Preface.

Table of Contents.

About the Editor.

Area Editors.

List of Contributors.

1: Abelian Hidden Subgroup Problem.

2: Adaptive Partitions.

3: Adwords Pricing.

4: Algorithm DC–Tree for k Servers on Trees.

5: Algorithmic Cooling.

6: Algorithmic Mechanism Design.

7: Algorithms for Spanners in Weighted Graphs.

8: All Pairs Shortest Paths in Sparse Graphs.

9: All Pairs Shortest Paths via Matrix Multiplication.

10: Alternative Performance Measures in Online Algorithms.

11: Analyzing Cache Misses.

12: Applications of Geometric Spanner Networks.

13: Approximate Dictionaries.

14: Approximate Regular Expression Matching.

15: Approximate Tandem Repeats.

16: Approximating Metric Spaces by Tree Metrics.

17: Approximations of Bimatrix Nash Equilibria.

18: Approximation Schemes for Bin Packing.

19: Approximation Schemes for Planar Graph Problems.

20: Arbitrage in Frictional Foreign Exchange Market.

21: Arithmetic Coding for Data Compression.

22: Assignment Problem.

23: Asynchronous Consensus Impossibility.

24: Atomic Broadcast.

25: Attribute–Efficient Learning.

26: Automated Search Tree Generation.

27: Backtracking Based k–SAT Algorithms.

28: Best Response Algorithms for Selfish Routing.

29: Bidimensionality.

30: Binary Decision Graph.

31: Bin Packing.

32: Boosting Textual Compression.

33: Branchwidth of Graphs.

34: Broadcasting in Geometric Radio Networks.

35: B–trees.

36: Burrows–Wheeler Transform.

37: Byzantine Agreement.

38: Cache–Oblivious B–Tree.

39: Cache–Oblivious Model.

40: Cache–Oblivious Sorting.

41: Causal Order, Logical Clocks, State Machine Replication.

42: Certificate Complexity and Exact Learning.

43: Channel Assignment and Routing in Multi-Radio Wireless Mesh Networks.

44: Circuit Partitioning: A Network-Flow-Based Balanced Min-Cut Approach.

45: Circuit Placement.

46: Circuit Retiming.

47: Circuit Retiming: An Incremental Approach.

48: Clock Synchronization.

49: Closest String and Substring Problems.

50: Closest Substring.

51: Color Coding.

52: Communication in Ad Hoc Mobile Networks Using Random Walks.

53: Competitive Auction.

54: Complexity of Bimatrix Nash Equilibria.

55: Complexity of Core.

56: Compressed Pattern Matching.

57: Compressed Suffix Array.

58: Compressed Text Indexing.

59: Compressing Integer Sequences and Sets.

60: Computing Pure Equilibria in the Game of Parallel Links.

61: Concurrent Programming, Mutual Exclusion.

62: Connected Dominating Set.

63: Connectivity and Fault-Tolerance in Random Regular Graphs.

64: Consensus with Partial Synchrony.

65: Constructing a Galled Phylogenetic Network.

66: CPU Time Pricing.

67: Critical Range for Wireless Networks.

68: Cryptographic Hardness of Learning.

69: Cuckoo Hashing.

70: Data Migration.

71: Data Reduction for Domination in Graphs.

72: Decoding Reed-Solomon Codes.

73: Decremental All-Pairs Shortest Paths.

74: Degree-Bounded Planar Spanner with Low Weight.

75: Degree-Bounded Trees.

76: Deterministic Broadcasting in Radio Networks.

77: Deterministic Searching on the Line.

78: Dictionary-Based Data Compression.

79: Dictionary Matching and Indexing (Exact and with Errors).

80: Dilation of Geometric Networks.

81: Directed Perfect Phylogeny (Binary Characters).

82: Direct Routing Algorithms.

83: Distance–Based Phylogeny Reconstruction (Fast–Converging).

84: Distance–Based Phylogeny Reconstruction (Optimal Radius).

85: Distributed Algorithms for Minimum Spanning Trees.

86: Distributed Vertex Coloring.

87: Dynamic Trees.

88: Edit Distance under Block Operations.

89: Efficient Methods for Multiple Sequence Alignment with Guaranteed Error Bounds.

90: Engineering Algorithms for Computational Biology.

91: Engineering Algorithms for Large Network Applications.

92: Engineering Geometric Algorithms.

93: Equivalence Between Priority Queues and Sorting.

94: Euclidean Traveling Salesperson Problem.

95: Exact Algorithms for Dominating Set.

96: Exact Algorithms for General CNF SAT.

97: Exact Graph Coloring Using Inclusion–Exclusion.

98: Experimental Methods for Algorithm Analysis.

99: External Sorting and Permuting.

100: Facility Location.

101: Failure Detectors.

102: False-Name-Proof Auction.

103: Fast Minimal Triangulation.

104: Fault-Tolerant Quantum Computation.

105: Floorplan and Placement.

106: Flow Time Minimization.

107: FPGA Technology Mapping.

108: Fractional Packing and Covering Problems.

109: Fully Dynamic All Pairs Shortest Paths.

110: Fully Dynamic Connectivity.

111: Fully Dynamic Connectivity: Upper and Lower Bounds.

112: Fully Dynamic Higher Connectivity.

113: Fully Dynamic Higher Connectivity for Planar Graphs.

114: Fully Dynamic Minimum Spanning Trees.

115: Fully Dynamic Planarity Testing.

116: Fully Dynamic Transitive Closure.

117: Gate Sizing.

118: General Equilibrium.

119: Generalized Steiner Network.

120: Generalized Two-Server Problem.

121: Generalized Vickrey Auction.

122: Geographic Routing.

123: Geometric Dilation of Geometric Networks.

124: Geometric Spanners.

125: Gomory-Hu Trees.

126: Graph Bandwidth.

127: Graph Coloring.

128: Graph Connectivity.

129: Graph Isomorphism.

130: Greedy Approximation Algorithms.

131: Greedy Set-Cover Algorithms.

132: Hamilton Cycles in Random Intersection Graphs.

133: Hardness of Proper Learning.

134: High Performance Algorithm Engineering for Large-scale Problems.

135: Hospitals/Residents Problem.

136: Implementation Challenge for Shortest Paths.

137: Implementation Challenge for TSP Heuristics.

138: Implementing Shared Registers in Asynchronous Message-Passing Systems.

139: Incentive Compatible Selection.

140: Independent Sets in Random Intersection Graphs.

141: Indexed Approximate String Matching.

142: Inductive Inference.

143: I/O-Model.

144: Kinetic Data Structures.

145: Knapsack.

146: Learning with the Aid of an Oracle.

147: Learning Automata.

148: Learning Constant-Depth Circuits.

149: Learning DNF Formulas.

150: Learning Heavy Fourier Coefficients of Boolean Functions.

151: Learning with Malicious Noise.

152: Learning Significant Fourier Coefficients over Finite Abelian Groups.

153: LEDA: a Library of Efficient Algorithms.

154: Leontief Economy Equilibrium.

155: Linearity Testing/Testing Hadamard Codes.

156: Linearizability.

157: List Decoding Near Capacity: Folded RS Codes.

158: List Scheduling.

159: Load Balancing.

160: Local Alignment (with Affine Gap Weights).

161: Local Alignment (with Concave Gap Weights).

162: Local Approximation of Covering and Packing Problems.

163: Local Computation in Unstructured Radio Networks.

164: Local Search Algorithms for kSAT.

165: Local Search for K-medians and Facility Location.

166: Lower Bounds for Dynamic Connectivity.

167: Low Stretch Spanning Trees.

168: LP Decoding.

169: Majority Equilibrium.

170: Market Games and Content Distribution.

171: Max Cut.

172: Maximum Agreement Subtree (of 2 Binary Trees).

173: Maximum Agreement Subtree (of 3 or More Trees).

174: Maximum Agreement Supertree.

175: Maximum Compatible Tree.

176: Maximum-Density Segment.

177: Maximum Matching.

178: Maximum-scoring Segment with Length Restrictions.

179: Maximum Two-Satisfiability.

180: Max Leaf Spanning Tree.

181: Metrical Task Systems.

182: Metric TSP.

183: Minimum Bisection.

184: Minimum Congestion Redundant Assignments.

185: Minimum Energy Broadcasting in Wireless Geometric Networks.

186: Minimum Energy Cost Broadcasting in Wireless Networks.

187: Minimum Flow Time.

188: Minimum Geometric Spanning Trees.

189: Minimum k-Connected Geometric Networks.

190: Minimum Makespan on Unrelated Machines.

191: Minimum Spanning Trees.

Front Cover.

Half Title Page.

Title Page.

Copyright Page.

Preface.

Table of Contents.

About the Editor.

Area Editors.

List of Contributors.

1: Abelian Hidden Subgroup Problem.

2: Adaptive Partitions.

3: Adwords Pricing.

4: Algorithm DC–Tree for k Servers on Trees.

5: Algorithmic Cooling.

6: Algorithmic Mechanism Design.

7: Algorithms for Spanners in Weighted Graphs.

8: All Pairs Shortest Paths in Sparse Graphs.

9: All Pairs Shortest Paths via Matrix Multiplication.

10: Alternative Performance Measures in Online Algorithms.

11: Analyzing Cache Misses.

12: Applications of Geometric Spanner Networks.

13: Approximate Dictionaries.

14: Approximate Regular Expression Matching.

15: Approximate Tandem Repeats.

16: Approximating Metric Spaces by Tree Metrics.

17: Approximations of Bimatrix Nash Equilibria.

18: Approximation Schemes for Bin Packing.

19: Approximation Schemes for Planar Graph Problems.

20: Arbitrage in Frictional Foreign Exchange Market.

21: Arithmetic Coding for Data Compression.

22: Assignment Problem.

23: Asynchronous Consensus Impossibility.

24: Atomic Broadcast.

25: Attribute–Efficient Learning.

26: Automated Search Tree Generation.

27: Backtracking Based k–SAT Algorithms.

28: Best Response Algorithms for Selfish Routing.

29: Bidimensionality.

30: Binary Decision Graph.

31: Bin Packing.

32: Boosting Textual Compression.

33: Branchwidth of Graphs.

34: Broadcasting in Geometric Radio Networks.

35: B–trees.

36: Burrows–Wheeler Transform.

37: Byzantine Agreement.

38: Cache–Oblivious B–Tree.

39: Cache–Oblivious Model.

40: Cache–Oblivious Sorting.

41: Causal Order, Logical Clocks, State Machine Replication.

42: Certificate Complexity and Exact Learning.

43: Channel Assignment and Routing in Multi-Radio Wireless Mesh Networks.

44: Circuit Partitioning: A Network-Flow-Based Balanced Min-Cut Approach.

45: Circuit Placement.

46: Circuit Retiming.

47: Circuit Retiming: An Incremental Approach.

48: Clock Synchronization.

49: Closest String and Substring Problems.

50: Closest Substring.

51: Color Coding.

52: Communication in Ad Hoc Mobile Networks Using Random Walks.

53: Competitive Auction.

54: Complexity of Bimatrix Nash Equilibria.

55: Complexity of Core.

56: Compressed Pattern Matching.

57: Compressed Suffix Array.

58: Compressed Text Indexing.

59: Compressing Integer Sequences and Sets.

60: Computing Pure Equilibria in the Game of Parallel Links.

61: Concurrent Programming, Mutual Exclusion.

62: Connected Dominating Set.

63: Connectivity and Fault-Tolerance in Random Regular Graphs.

64: Consensus with Partial Synchrony.

65: Constructing a Galled Phylogenetic Network.

66: CPU Time Pricing.

67: Critical Range for Wireless Networks.

68: Cryptographic Hardness of Learning.

69: Cuckoo Hashing.

70: Data Migration.

71: Data Reduction for Domination in Graphs.

72: Decoding Reed-Solomon Codes.

73: Decremental All-Pairs Shortest Paths.

74: Degree-Bounded Planar Spanner with Low Weight.

75: Degree-Bounded Trees.

76: Deterministic Broadcasting in Radio Networks.

77: Deterministic Searching on the Line.

78: Dictionary-Based Data Compression.

79: Dictionary Matching and Indexing (Exact and with Errors).

80: Dilation of Geometric Networks.

81: Directed Perfect Phylogeny (Binary Characters).

82: Direct Routing Algorithms.

83: Distance–Based Phylogeny Reconstruction (Fast–Converging).

84: Distance–Based Phylogeny Reconstruction (Optimal Radius).

85: Distributed Algorithms for Minimum Spanning Trees.

86: Distributed Vertex Coloring.

87: Dynamic Trees.

88: Edit Distance under Block Operations.

89: Efficient Methods for Multiple Sequence Alignment with Guaranteed Error Bounds.

90: Engineering Algorithms for Computational Biology.

91: Engineering Algorithms for Large Network Applications.

92: Engineering Geometric Algorithms.

93: Equivalence Between Priority Queues and Sorting.

94: Euclidean Traveling Salesperson Problem.

95: Exact Algorithms for Dominating Set.

96: Exact Algorithms for General CNF SAT.

97: Exact Graph Coloring Using Inclusion–Exclusion.

98: Experimental Methods for Algorithm Analysis.

99: External Sorting and Permuting.

100: Facility Location.

101: Failure Detectors.

102: False-Name-Proof Auction.

103: Fast Minimal Triangulation.

104: Fault-Tolerant Quantum Computation.

105: Floorplan and Placement.

106: Flow Time Minimization.

107: FPGA Technology Mapping.

108: Fractional Packing and Covering Problems.

109: Fully Dynamic All Pairs Shortest Paths.

110: Fully Dynamic Connectivity.

111: Fully Dynamic Connectivity: Upper and Lower Bounds.

112: Fully Dynamic Higher Connectivity.

113: Fully Dynamic Higher Connectivity for Planar Graphs.

114: Fully Dynamic Minimum Spanning Trees.

115: Fully Dynamic Planarity Testing.

116: Fully Dynamic Transitive Closure.

117: Gate Sizing.

118: General Equilibrium.

119: Generalized Steiner Network.

120: Generalized Two-Server Problem.

121: Generalized Vickrey Auction.

122: Geographic Routing.

123: Geometric Dilation of Geometric Networks.

124: Geometric Spanners.

125: Gomory-Hu Trees.

126: Graph Bandwidth.

127: Graph Coloring.

128: Graph Connectivity.

129: Graph Isomorphism.

130: Greedy Approximation Algorithms.

131: Greedy Set-Cover Algorithms.

132: Hamilton Cycles in Random Intersection Graphs.

133: Hardness of Proper Learning.

134: High Performance Algorithm Engineering for Large-scale Problems.

135: Hospitals/Residents Problem.

136: Implementation Challenge for Shortest Paths.

137: Implementation Challenge for TSP Heuristics.

138: Implementing Shared Registers in Asynchronous Message-Passing Systems.

139: Incentive Compatible Selection.

140: Independent Sets in Random Intersection Graphs.

141: Indexed Approximate String Matching.

142: Inductive Inference.

143: I/O-Model.

144: Kinetic Data Structures.

145: Knapsack.

146: Learning with the Aid of an Oracle.

147: Learning Automata.

148: Learning Constant-Depth Circuits.

149: Learning DNF Formulas.

150: Learning Heavy Fourier Coefficients of Boolean Functions.

151: Learning with Malicious Noise.

152: Learning Significant Fourier Coefficients over Finite Abelian Groups.

153: LEDA: a Library of Efficient Algorithms.

154: Leontief Economy Equilibrium.

155: Linearity Testing/Testing Hadamard Codes.

156: Linearizability.

157: List Decoding Near Capacity: Folded RS Codes.

158: List Scheduling.

159: Load Balancing.

160: Local Alignment (with Affine Gap Weights).

161: Local Alignment (with Concave Gap Weights).

162: Local Approximation of Covering and Packing Problems.

163: Local Computation in Unstructured Radio Networks.

164: Local Search Algorithms for kSAT.

165: Local Search for K-medians and Facility Location.

166: Lower Bounds for Dynamic Connectivity.

167: Low Stretch Spanning Trees.

168: LP Decoding.

169: Majority Equilibrium.

170: Market Games and Content Distribution.

171: Max Cut.

172: Maximum Agreement Subtree (of 2 Binary Trees).

173: Maximum Agreement Subtree (of 3 or More Trees).

174: Maximum Agreement Supertree.

175: Maximum Compatible Tree.

176: Maximum-Density Segment.

177: Maximum Matching.

178: Maximum-scoring Segment with Length Restrictions.

179: Maximum Two-Satisfiability.

180: Max Leaf Spanning Tree.

181: Metrical Task Systems.

182: Metric TSP.

183: Minimum Bisection.

184: Minimum Congestion Redundant Assignments.

185: Minimum Energy Broadcasting in Wireless Geometric Networks.

186: Minimum Energy Cost Broadcasting in Wireless Networks.

187: Minimum Flow Time.

188: Minimum Geometric Spanning Trees.

189: Minimum k-Connected Geometric Networks.

190: Minimum Makespan on Unrelated Machines.

191: Minimum Spanning Trees.