Cengage Learning

Encyclopedia of Algorithms, 1st Edition

  • Published By:
  • ISBN-10: 0387301623
  • ISBN-13: 9780387301624
  • Grade Level Range: College Freshman - College Senior
  • 1166 Pages | eBook
  • Original Copyright 2007 | Published/Released October 2008
  • This publication's content originally published in print form: 2007

    • Pricing for eBooks is based on your account type and population served. Accurate pricing will only display for registered users. Click here to register. Once registered, you will receive an email confirmation and can shop for titles with accurate pricing applied to your order. If you choose not to register, please call your sales representative at 1.800.877.4253 or email galeord@cengage.com.

  • Price:  Sign in for price

About

Overview

Provides researchers, students, and practitioners of algorithmic research with a mechanism to efficiently and accurately find the names, definitions, key results, and further readings of important algorithmic problems.

Table of Contents

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.