第1页 / 共2428页
第2页 / 共2428页
第3页 / 共2428页
第4页 / 共2428页
第5页 / 共2428页
第6页 / 共2428页
第7页 / 共2428页
第8页 / 共2428页
Encyclopedia of Algorithms, Second Edition [2016].pdf
Encyclopedia of Algorithms
Preface
About the Editor
Area Editors
Contributors
A
Abelian Hidden Subgroup Problem
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Discussion: What About Non-Abelian Groups?
Cross-References
Recommended Reading
Abstract Voronoi Diagrams
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Generalizations
Cross-References
Recommended Reading
Active Learning – Modern Learning Theory
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Formal Setup
Key Results
Disagreement-Based Active Learning
Margin-Based Active Learning
Cluster-Based Active Learning
Cross-References
Recommended Reading
Active Self-Assembly and Molecular Robotics with Nubots
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Open Problems
The Complexity of Assembling Lines
Computational Power
Synchronization and Composition of Nubot Algorithms
Agitation Versus the Movement Rule
Intrinsic Universality and Simulation
Brownian Nubots
Cross-References
Recommended Reading
Adaptive Partitions
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Historical Note
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Additive Spanners
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Open Problems
Recommended Reading
Adwords Pricing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Algorithm DC-Tree for k-Servers on Trees
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Algorithmic Cooling
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Basic Concepts
Loss-Less In-Place Data Compression
Spin Temperature, Polarization Bias, and Effective Cooling
Key Results
Molecular-Scale Heat Engines
Heat-Bath Algorithmic Cooling
Practicable Algorithmic Cooling
Exhaustive Algorithmic Cooling
Other Results
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Algorithmic Mechanism Design
Years and Authors of Summarized Original Work
Problem Definition
A Motivating Example: Shortest Paths
Abstract Formulation
Key Results
Problem Domain 1: Job Scheduling
Problem Domain 2: Digital Goods and Revenue Maximization
Problem Domain 3: Combinatorial Auctions
Problem Domain 4: Online Auctions
Advanced Issues
Monotonicity
Impossibilities of truthful design
Alternative solution concepts
Applications
Cross-References
Recommended Reading
Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
URLs to Code and Data Sets
Cross-References
Recommended Reading
All Pairs Shortest Paths in Sparse Graphs
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Definition of Distance
Classic Algorithms
Integer-Weighted Graphs
Key Results
Applications
Open Problems
Experimental Results
Data Sets
URL to Code
Cross-References
Recommended Reading
All Pairs Shortest Paths via Matrix Multiplication
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Alon-Galil-Margalit Algorithm
Takaoka Algorithm
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
All-Distances Sketches
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Preprocessing Cost
Supported Queries
Key Results
Definition
Relation to MinHash Sketches
Direction
Node Weights
Algorithms
Estimation
Distance Distribution
Closeness Centrality (Distance-Decaying)
Closeness Similarity and Influence
Approximate Distance Oracles
Applications
Extensions
Cross-References
Recommended Reading
Alternate Parameterizations
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Structural Parameterizations
Above or Below Guarantee Parameterizations
Key Results
Open Problems
Cross-References
Recommended Reading
Alternative Performance Measures in Online Algorithms
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Relative Worst-Order Ratio
Loose Competitiveness
Diffuse Adversary Model
Bijective Analysis
Smoothed Competitiveness
Search Ratio
Cross-References
Recommended Reading
Amortized Analysis on Enumeration Algorithms
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Amortization by Children
Push-Out Amortization
Push-Out Condition (PO Condition) T(X) ≥αT(X) - β(|C(X)|+1)T*
Matching Enumeration
Elimination Ordering
Recommended Reading
AMS Sketch
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Data Structure Description
Applications
URLs to Code and Data Sets
Cross-References
Recommended Reading
Analyzing Cache Behaviour in Multicore Architectures
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Paging
Paging in Multicore Caches
Key Results
Online Paging
Offline Paging
Other Models
Open Problems
Cross-References
Recommended Reading
Analyzing Cache Misses
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Caches, Models, and Cache Analysis
Related Problems
Key Results
Multiple Sequence Access with Additional Working Set
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Applications of Geometric Spanner Networks
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notation and Definitions
Survey of Related Research
Key Results
Pruning
Bucketing
Main Results
Applications
Open Problems
Cross-References
Recommended Reading
Approximate Dictionaries
Keywords
Years and Authors of Summarized Original Work
Problem Definition
The Problem and the Model
Related Work
Key Results
Randomized Schemes with Two-Sided Error
Randomized Schemes with One-Sided Error
Deterministic Schemes
Power of Few Bitprobes
Applications
Recommended Reading
Approximate Distance Oracles with Improved Query Time
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Oracle with O(log k) Query Time
Oracle with Constant Query Time
Applications
Open Problems
Recommended Reading
Approximate Matching
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Algorithms for Exact MWM
Approximate Matching
Key Results
Approximate Maximum Cardinality Matching
Approximate Maximum Weighted Matching
Applications
Cross-References
Recommended Reading
Approximate Regular Expression Matching
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Experimental Results
URL to Code
Cross-References
Recommended Reading
Approximate String Matching
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Experimental Results
URL to Code
Cross-References
Recommended Reading
Approximate Tandem Repeats
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
URL to Code
Cross-References
Recommended Reading
Approximating Fixation Probabilities in the Generalized Moran Process
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Bounding the Fixation Probability
Bounding the Absorption Time
Approximation Algorithms
Recommended Reading
Approximating Metric Spaces by Tree Metrics
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notations
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Approximating the Diameter
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Open Problems
Recommended Reading
Approximating the Partition Function of Two-Spin Systems
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Ferromagnetic Two-Spin Systems
Antiferromagnetic Two-Spin Systems
Algorithms for Graphs with Bounded Connective Constant
Cross-References
Recommended Reading
Approximation Schemes for Bin Packing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notations
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Approximation Schemes for Geometric Network Optimization Problems
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Overview of Methods
Arora's Dissection Method
The m-Guillotine Method
Generalizations to Other Metrics
Applications to Network Optimization
Open Problems
Cross-References
Recommended Reading
Approximation Schemes for Makespan Minimization
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
The Dual Approximation Framework and Common Preprocessing Steps
The Case of Identical Machines
The Case of Related Machines
Cross-References
Recommended Reading
Approximation Schemes for Planar Graph Problems
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Approximations of Bimatrix Nash Equilibria
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notation
Bimatrix Games
Approximate Nash Equilibria
Key Results
Applications
Recommended Reading
Arbitrage in Frictional Foreign Exchange Market
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Recommended Reading
Arithmetic Coding for Data Compression
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Modeling
Implementation Issues
Incremental Output
Use of Integer Arithmetic
Limited-Precision Arithmetic Coding
Applications
Open Problems
Experimental Results
Data Sets
URL to Code
Cross-References
Recommended Reading
Assignment Problem
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
High-Level Description
More Efficient Implementation
Applications
Open Problems
Recommended Reading
Asynchronous Consensus Impossibility
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Terminology
Key Results
Applications
Open Problems
Related Work
Cross-References
Recommended Reading
Atomic Broadcast
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Related Work
Notations and Assumptions
Problem Definition
Key Results
Atomic Broadcast for Omission Failures
Atomic Broadcast for Timing Failures
Atomic Broadcast for Byzantine Failures
Bounds
Applications
Cross-References
Recommended Reading
Attribute-Efficient Learning
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Cross-References
Recommended Reading
Automated Search Tree Generation
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Analysis
Case Distinction
Key Results
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
B
Backdoors to SAT
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Backtracking Based k-SAT Algorithms
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notation
Key Results
ResolveSat Algorithm
Analysis of ResolveSat
Applications
Open Problems
Cross-References
Recommended Reading
Bargaining Networks
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Solution Concept
Feasible Solution
Outside Option
Stable Solution
Balanced Solution
Key Results
Existence of Stable and Balanced Solutions
Cooperative Game Theory Perspective
Core
Prekernel
Nucleolus
Finding Stable and Balanced Solutions
Open Problems
Cross-References
Recommended Reading
Bend Minimization for Orthogonal Drawings of Plane Graphs
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Bend Minimization Problem
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Best Response Algorithms for Selfish Routing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
The Model
Best Response
Flows and Common Best Response
Layered and Series-Parallel Graphs
Key Results
The Greedy Best Response Algorithm (GBR)
The Characterization
Applications
Open Problems
Cross-References
Recommended Reading
Beyond Evolutionary Trees
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Consensus Network Reconstruction
Reconciliation of Gene Trees and Species Trees
Key Results
Consensus Networks
Reconciliation
Open Problems
Cross-References
Recommended Reading
Beyond Hypergraph Dualization
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Strong Duality
Weak Duality
Complexity
Applications
Frequent Conjunctive Queries
Rigid Sequences
Open Problems
URLs to Code and Data Sets
Cross-References
Recommended Reading
Beyond Worst Case Sensitivity in Private Data Analysis
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Computing the Median: A Motivating Example
Notions of Sensitivity
Global Sensitivity [11]
Local Sensitivity
Smooth Sensitivity
[11]
Key Results
Algorithm 1: Smooth Sensitivity Based
Algorithm 2: Propose-Test-Release (PTR) Framework
Application 1: Computing the Median
Application 2: Selection from a Discrete Set
Reference Notes
Recommended Reading
BG Distributed Simulation Algorithm
Keywords
Years and Authors of Summarized Original Work
Problem Definition
System Model
Processes
Failure Model
Communication
Tasks
Simulation
Key Results
Simulation of Memory
The Safe-Agreement Object
Overview of the Simulation
Applications
Recommended Reading
Bidimensionality
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Graph Classes
Bidimensional Parameters
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Bin Packing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Worst-Case Behavior
Asymptotic Worst-Case Ratios
Online Algorithms
Bounded-Space Algorithms
Average-Case Behavior
Continuous Distributions
Discrete Distributions
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Bin Packing with Cardinality Constraints
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Problem 1 (Bin Packing with Cardinality Constraints)
Key Results
Approximation Algorithms
Online Algorithms
Bounded-Space Online Algorithms
Applications
Open Problems
Cross-References
Recommended Reading
Bin Packing, Variants
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Cross-References
Recommended Reading
Binary Decision Graph
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Boolean Functions
Boolean Circuits
Boolean Formulas
Shannon Trees
Key Results
Definitions
BDD Operations
Variable Ordering
Applications
Experimental Results
Data Sets
URL to Code
Cross-References
Recommended Reading
Binary Space Partitions
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Line Segments in the Plane
Simplices in Rd
Axis-Parallel Segments, Rectangles, and Hyperrectangles
Tilings
Applications
Open Problems
Recommended Reading
Block Shaping in Floorplan
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Boosting Textual Compression
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Notation: The Empirical Entropy
The Burrows-Wheeler Transform
The Compression Boosting Algorithm
Applications
Open Problems
Experimental Results
Data Sets
URL to Code
Cross-References
Recommended Reading
Branchwidth of Graphs
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Definition
Key Results
Algorithms for Branchwidth
Applications
Open Problems
Cross-References
Recommended Reading
Broadcast Scheduling – Minimizing Average Response Time
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Linear Programming Formulation
Rounding Techniques
The Half-Integrality Assumption
Viewing the LP Solution as a Convex Combination of Blocks
Rounding the Solution to Minimize Backlog: Attempt 1 [1]
Rounding the Solution to Minimize Backlog: Attempt 2 [3]
Rounding the Solution to Minimize Backlog: Attempt 3 [2]
Hardness Results
Online Broadcast Scheduling
Recommended Reading
Broadcasting in Geometric Radio Networks
Keywords
Synonyms
Years and Authors of Summarized Original Work
Problem Definition
The Model Overview
The Problem
Terminology and Notation
Related Work
Key Results
Arbitrary GRN in the Model Without Collision Detection
Large Knowledge Radius
Knowledge Radius Zero
Symmetric GRN
The Model with Collision Detection
The Model Without Collision Detection
Applications
Open Problems
Cross-References
Recommended Reading
B-trees
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notations
Variants and Extensions
Update Operations
Key Results
Applications
Databases
Priority Queues
Buffered Data Structures
B-trees as Base Structures
Amortized Analysis
URLs to Code and Data Sets
Cross-References
Recommended Reading
Burrows-Wheeler Transform
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Notation
The Burrows-Wheeler Transform
Algorithmic Issues
The Burrows-Wheeler Compression Algorithm
Applications
Open Problems
Experimental Results
Data Sets
URL to Code
Cross-References
Recommended Reading
Byzantine Agreement
Keywords
Years and Authors of Summarized Original Work
Problem Definition
System Model
Definition of the Byzantine Agreement Problem
Timing Model
Overview
Key Results
Crash Failures
Omission Failures
Byzantine Failures with Authentication
Byzantine Failures Without Authentication
Arbitrary Network Topologies
Interactive Consistency and Byzantine Generals
Firing Squad
General Translation Techniques
Applications
Cross-References
Recommended Reading
C
Cache-Oblivious B-Tree
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Cache-Oblivious Model
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Experimental Results
Cross-References
Recommended Reading
Cache-Oblivious Sorting
Keywords
Problem Definition
Model
Sorting
Key Results
Funnelsort
Implicit Cache-Oblivious Sorting
The Role of the Tall Cache Assumption
Applications
Open Problems
Experimental Results
URL to Code
Cross-References
Recommended Reading
Cache-Oblivious Spacetree Traversals
Keywords
Years and Authors of Summarized Original Work
Background
Problem Definition
Key Results
Space-Filling Curve Orders on Tree-Structured Grids
Space-Filling-Curve Traversals
SFC Traversals in the Cache-Oblivious Model
Multiscale Depth-First and Breadth-First Traversals
Toward Parallel Tree Traversals
Recursion Unrolling and Parallelism
Other Tree-Structured Meshes and Space-Filling Curves
Applications
Cross-References
Recommended Reading
Canonical Orders and Schnyder Realizers
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Canonical Order
Schnyder Realizer
Drawing Planar Graphs
Equivalency of Canonical Orders and Schnyder Realizers
Cross-References
Recommended Reading
Causal Order, Logical Clocks, State Machine Replication
Keywords
Years and Authors of Summarized Original Work
Problem Definition
System Model
Causal Order
Logical Clocks
State Machine Replication
Key Results
Logical Clocks
State Machine Replication
Applications
Cross-References
Recommended Reading
Certificate Complexity and Exact Learning
Keywords
Years and Authors of Summarized Original Work
Problem Definition
The Exact Learning Model
Query Complexity of Exact Learning
Improper Learning and the Halving Algorithm
Proper Learning and Certificates
Key Results
Open Problems
Cross-References
Recommended Reading
Channel Assignment and Routing in Multi-Radio Wireless Mesh Networks
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Joint Routing, Channel Assignment, and Link Scheduling Algorithm
A Linear Programming-Based Routing Algorithm
Channel Assignment
Link Flow Scheduling
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Circuit Partitioning: A Network-Flow-Based Balanced Min-Cut Approach
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Optimal-Network-Flow-Based Min-Net-Cut Bipartition
Min-Cut Balanced-Bipartition Heuristic
Applications
Experimental Results
Cross-References
Recommended Reading
Circuit Placement
Keywords
Synonyms
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Combinatorial Techniques for Wire Length Minimization
Quadratic and Nonlinear Wire Length Approximations
Quadratic, Linearized Quadratic, and Bound-to-Bound Placement
Half-perimeter Wire Length Placement:
Analytic Techniques for Target Density Constraints
Force-Based Spreading
Fixed-Point Spreading
Generalized Force-Directed Spreading
Potential Function Spreading
Applications
Experimental Results and Data Sets
Cross-References
Recommended Reading
Circuit Retiming
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notations
Constraints
Key Results
Applications
Experimental Results
Cross-References
Recommended Reading
Circuit Retiming: An Incremental Approach
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Experimental Results
Cross-References
Recommended Reading
Clique Enumeration
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Efficient Algorithms for Clique Enumeration
Applications
Experimental Results
Cross-References
Recommended Reading
Clock Synchronization
Years and Authors of Summarized Original Work
Problem Definition
Background and Overview
Formal Model
Algorithms
Problem Statement
Key Results
Later Developments
Applications
Open Problems
Cross-References
Recommended Reading
Closest String and Substring Problems
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Applications
A More General Problem
Open Problems
Recommended Reading
Closest Substring
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Clustered Graph Drawing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Open Problems
Cross-References
Recommended Reading
Clustering Under Stability Assumptions
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Related Notions
Open Problems
Recommended Reading
Color Coding
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Method Description
Derandomization
Key Results
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Colouring Non-sparse Random Intersection Graphs
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
An Efficient Algorithm
Coloring Random Hypergraphs
Applications
Open Problems
Recommended Reading
Combinatorial Gray Code
Keywords
Years and Authors of Summarized Original Work
Problem Definition
The Binary Reflected Gray Codes
Combinations as Represented by Bit Strings
Generating Permutations via Plain Changes
Hamiltonicity
The Representation Issue
Algorithmic Issues
CAT Algorithms, Loopless Algorithms
Key Results
Numerical Partitions [5,
9]
Spanning Trees
Basic Words of Antimatroids [7]
Words in a Bubble Language [8,
11]
Permutations via σ and τ [16]
Middle Two Levels of the Boolean Lattice [6]
URLs to Code and Data Sets
Cross-References
Recommended Reading
Combinatorial Optimization and Verification in Self-Assembly
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Tile Assembly Models
Key Results
Minimum Tile Set Problem
Concentration Optimization
Assembly Verification
Open Problems
Cross-References
Recommended Reading
Communication Complexity
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Problem-Specific Results
Equality Testing
Comparison
Indexing and Bipartite Pointer Jumping
Inner Product Parity
Set Disjointness
Gap Hamming Distance
General Complexity-Theoretic Results
Determinism vs. Public vs. Private Randomness
The Log-Rank Conjecture and Further Matrix Analysis
Direct Sum, Direct Product, and Amortization
Round Elimination
Applications
Data Stream Algorithms
Data Structures
Circuit Complexity
Further Applications
Recommended Reading
Communication in Ad Hoc Mobile Networks Using Random Walks
Keywords
Years and Authors of Summarized Original Work
Problem Definition
The Motion Space
The Motion of the Nodes-Adversaries
Key Results
Applications
Related Work
Open Problems
Experimental Results
URL to Code
Cross-References
Recommended Reading
Compact Routing Schemes
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Open Problems
Recommended Reading
Competitive Auction
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Cross-References
Recommended Reading
Complexity Dichotomies for Counting Graph Homomorphisms
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Experimental Results
URLs to Code and Data Sets
Cross-References
Recommended Reading
Complexity of Bimatrix Nash Equilibria
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Complexity of Core
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Cross-References
Recommended Reading
Compressed Document Retrieval on String Collections
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Notations and Basic Framework
An Index of Size 2|CSA| Bits
Space-Optimal Index
Cross-References
Recommended Reading
Compressed Range Minimum Queries
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Indexing Versus Encoding Model
Model of Computation
Key Results
Extensions
Surpassing the Lower Bound
Top-k Queries
Range Selection
Higher Dimensions
Further Extensions
Applications
Cross-References
Recommended Reading
Compressed Representations of Graphs
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Outerplanar, Planar, and k-Page Graphs
Arbitrary Directed Graphs, DAGs, Undirected Graphs, and Posets
Cross-References
Recommended Reading
Compressed Suffix Array
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Ψ-Based CSAs
FM-Index
Cross-References
Recommended Reading
Compressed Suffix Trees
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Objective
Key Results
Classical Results
Succinct Results
Applications
Experimental Results
URLs to Code and Data Sets
Cross-References
Recommended Reading
Compressed Text Indexing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
URL to Code and Data Sets
Cross-References
Recommended Reading
Compressed Tree Representations
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Preliminaries
Key Results
LOUDS
BP Representation
DFUDS
Fully Functional BP Representation
Other Representations
Applications
Open Problems
Experimental Results
URLs to Code and Data Sets
Cross-References
Recommended Reading
Compressing and Indexing Structured Text
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notation and Basic Facts
Key Results
Applications
Open Problems
Experimental Results
Data Sets
URL to Code
Cross-References
Recommended Reading
Compressing Integer Sequences
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Constraints
Key Results
Unary and Binary Codes
Elias Codes
Fibonacci-Based Codes
Byte-Aligned Codes
Golomb Codes
Other Static Codes
Elias-Fano Codes
Packed Codes
Context-Sensitive Codes
Applications
Cross-References
Recommended Reading
Computing Cutwidth and Pathwidth of Semi-complete Digraphs
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Recommended Reading
Computing Pure Equilibria in the Game of Parallel Links
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Subclasses of PLG
Algorithmic Questions Concerning PLG
Status of Problem 1
Status of Problem 2, 5 and 6
Status of Problem 3 and 4
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Concurrent Programming, Mutual Exclusion
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Concurrency, Synchronization and Resource Allocation
The Mutual Exclusion Problem
Key Results
Atomic Operations
Algorithms and Lower Bounds
Applications
Cross-References
Recommended Reading
Connected Dominating Set
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Historical Background
Key Results
Central Area
Boundary Area
Putting Together
Applications
Open Problems
Cross-References
Recommended Reading
Connected Set-Cover and Group Steiner Tree
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Open Problems
Cross-References
Recommended Reading
Connectivity and Fault Tolerance in Random Regular Graphs
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Configurations and Translation Lemmata
Multiconnectivity Properties of Gn,pr
Gn,pr Becomes Disconnected
Existence of a Giant Component in Gn,pr
Applications
Open Problems
Recommended Reading
Consensus with Partial Synchrony
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Partial Synchrony
Basic Round Model
Consensus Algorithm for Benign Faults (Requires f
Consensus Algorithm for Byzantine Faults (Requires f < n/3 )
The Special Case of Synchronous Communication
Implementation of the Basic Round Model
Upper Bound for Resiliency
Applications
Open Problems
Cross-References
Recommended Reading
Convex Graph Drawing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Convex Drawing Algorithm
Convex Testing Algorithm
Applications
Open Problems
Recommended Reading
Convex Hulls
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notation
Key Results
Lower Bound
Divide and Conquer by Preparata and Hong [8]
Graham Scan [4]
Jarvis's March or Gift Wrapping [5]
Chan's Algorithm [2]
Implementation
Cross-References
Recommended Reading
Coordinated Sampling
Keywords
Years and Authors of Summarized Original Work
Problem Definition
What Is Sample Coordination?
Why Use Coordination?
Co-located Data
Dispersed Data
Implicit Data
Key Results
Applications
Recommended Reading
Counting by ZDD
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Constraints
Key Results
BDDs/ZDDs for Graph Enumeration
Frontier-Based Method
Applications
Open Problems
Experimental Results
A Related YouTube Video
Graphillion: Open Software Library
URLs to Code and Data Sets
Recommended Reading
Counting Triangles in Graph Streams
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Outline of the Rest of the Article
Key Results
The Algorithm of [12] and Its Analysis
A key Algorithmic Tool: A Reservoir of Uniform Edges
A Key Analytical Tool: The Birthday Paradox
Related Work
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Count-Min Sketch
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Data Structure Description
Update Procedure
Point Queries
Range, Heavy Hitter, and Quantile Queries
Inner Product Queries
Conservative Update
Applications
Experimental Results
URLs to Code and Data Sets
Cross-Reference
Recommended Reading
CPU Time Pricing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notations
The CPU Job-Scheduling Problem
Key Results
Applications
Cross-References
Recommended Reading
Critical Range for Wireless Networks
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Cryptographic Hardness of Learning
Keywords
Years and Authors of Summarized Original Work
Problem Definition
PAC Learning
Cryptographic Primitives
Key Results
Relationship to Hardness Results for Proper Learning
Applications and Related Work
Open Problems
Cross-References
Recommended Reading
Cuckoo Hashing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Prehistory
Cuckoo Hashing
Generalizations of Cuckoo Hashing
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Current Champion for Online Bin Packing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Open Problems
Cross-References
Recommended Reading
Curve Reconstruction
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Closed Smooth Curves
Open Smooth Curves
Closed Curves with Corners
Open and Closed Curves with Corners
Noisy Sample Sets
Cross-References
Recommended Reading
D
Data Migration
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Notations and Lower Bounds
Data Migration Algorithm
Representatives for Big Sets
Representatives for Small Sets
Scheduling Migrations
Analysis
Applications
Data Migration in Storage Systems
Gossiping and Broadcasting
Open Problems
Experimental Results
URL to Code
Cross-References
Recommended Reading
Data Reduction for Domination in Graphs
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Data Stream Verification
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Streaming Verification Model
Costs
Differences Between Models
Summary of Models
Key Results
Annotated Data Streams
Streaming Interactive Proofs
Computationally Sound Protocols
Implementations
Detailed Example
Properties and Costs of the Sum-Check Protocol
The SIP for Frequency Moments
Open Problems
Cross-References
Recommended Reading
3D Conforming Delaunay Triangulation
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Cross-References
Recommended Reading
Decoding Reed–Solomon Codes
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Reed–Solomon Codes
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Decremental All-Pairs Shortest Paths
Keywords
Years and Authors of Summarized Original Work
Problem Definition
History of the Problem
Key Results
Applications
URL to Code
Cross-References
Recommended Reading
Decremental Approximate-APSP in Directed Graphs
Keywords
Years and Authors of Summarized Original Work
Problem Definition
A History of Decremental APSP
Key Results
From Weighted Distances to Hop Distances
Shortcut Edges
Cross-References
Recommended Reading
Degree-Bounded Planar Spanner with Low Weight
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Cross-References
Recommended Reading
Degree-Bounded Trees
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Delaunay Triangulation and Randomized Constructions
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Delaunay Properties
Empty Ball Property
Size of the Triangulation
First Algorithms
Randomized Construction
Conflict Graph
Backward Analysis
Delaunay Hierarchy
A Less Randomized Construction
Experimental Results
URLs to Code and Data Sets
Cross-References
Recommended Reading
Derandomization of k-SAT Algorithm
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Notation
A Promise Version of k-SAT
Preliminaries: A Slower Algorithm
Speeding Up the Algorithm
k-ary Covering Codes
Cross-References
Recommended Reading
Deterministic Broadcasting in Radio Networks
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Recommended Reading
Deterministic Searching on the Line
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Extensions
Constraints
Key Results
Searching with No Information
Searching with an Upper Bound on the Target Distance
Applications
Cross-References
Recommended Reading
Dictionary Matching
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Text Indexing
Dictionary Matching
Dynamic Dictionary Matching
Text Indexing and Dictionary Matching with Errors
Approximate Text Indexing
Approximate Dictionary Matching
Text Indexing and Dictionary Matching Within (Small) Distance k
Applications
Cross-References
Recommended Reading
Dictionary-Based Data Compression
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
The LZ78 Algorithm
The LZ77 Algorithm
Entropy Bounds
Algorithmic Issues
Greedy vs. Non-Greedy Parsing
Applications
Prefetching
String Alignment
Compressed Full-Text Indexing
Substring Compression Problems
Grammar Generation
URL to Code
Cross-References
Recommended Reading
Differentially Private Analysis of Graphs
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Bibliographical Notes
Key Results
Focus on a ``Preferred Subset''
``Down'' Sensitivity
Lipschitz Extensions and Higher-Dimensional Releases
Applications
Open Problems
Cross-References
Recommended Reading
Dilation of Geometric Networks
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notations
Related Work
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Direct Routing Algorithms
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Hardness of Direct Routing
Direct Routing in General Graphs
Direct Routing in Specific Graphs
Tree
Mesh
Butterfly
Hypercube
Lower Bound for Buffering
Related Work
Applications
Cross-References
Recommended Reading
Directed Perfect Phylogeny (Binary Characters)
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Cross-References
Recommended Reading
Discrete Ricci Flow for Geometric Routing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Discrete Ricci Flow Algorithm
Discrete Hyperbolic Ricci Flow
Generalized Discrete Surface Ricci Flow
Applications
Open Problems
Experimental Results
URLs to Code and Data Sets
Recommended Reading
Distance Oracles for Sparse Graphs
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Open Problems
Recommended Reading
Distance-Based Phylogeny Reconstruction (Fast-Converging)
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Introduction
Formal Definitions
Popular Random Models
Neyman Model [14]
General Markov Model
Key Results
Applications
Cross-References
Recommended Reading
Distance-Based Phylogeny Reconstruction: Safety and Edge Radius
Keywords
Years and Authors of Summarized Original Work
Problem Definition
The Neighbor Joining (NJ) Algorithm of Saitou and Nei [18]
Balanced Minimum Evolution and Algorithms Inspired by It
The Fast Neighbor Joining (FNJ) Algorithm of Elias and Lagergren [7]
Safety Radius Performance Analysis (Atteson [1])
Key Results
Open Problems
Cross-References
Recommended Reading
Distributed Algorithms for Minimum Spanning Trees
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Distributed Computing for Enumeration
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Synchronization
Load Balancing
Data Locality
Applications
Open Problems
Cross-References
Recommended Reading
Distributed Randomized Broadcasting in Wireless Networks under the SINR Model
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
The Model with Strong Sensitivity and Strong Connectivity
The Model with Strong Sensitivity and Weak Connectivity
The Model with Weak Sensitivity and Strong Connectivity
The Model with Weak Sensitivity and Weak Connectivity
Applications
Open Problems
Cross-References
Recommended Reading
Distributed Snapshots
Keywords
Years and Authors of Summarized Original Work
Preliminary Remark
The Notion of a Global State
Modeling the Execution of a Process: The Event Point of View
Modeling the Execution of a Process: The Local State Point of View
Orphan and In-Transit Messages
Consistent Global State
The Lattice of Global States
Problem Definition
Specification of the Computation of a Consistent Global State
Principles of CGS Algorithms
Key Result 1: Chandy-Lamport's Algorithm
Assumption
The Algorithm in Two Rules
Properties of the Computed Global State
The Inherent Uncertainty on the Computed Global State
Message-Passing Snapshot Versus Shared Memory Snapshot
Other Assumptions and Algorithms
Key Result 2: A Necessary and Sufficient Condition
The Issue
The Result
Applications: Global Snapshots in Action
Detection of Stable Properties
Checkpointing
Cross-References
Recommended Reading
Distributed Vertex Coloring
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Experimental Results
Data Sets
Cross-References
Recommended Reading
Document Retrieval on String Collections
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Document Listing Problem
Top-k Document Retrieval
External Memory Document Retrieval
Cross-References
Recommended Reading
Double Partition
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Objective
Constraints
Problem 1 (Minimum Weight Connected Dominating Set in Unit Disk Graph)
Key Results
Double Partition Technique
MWDS in K × K Squares
MWDC for the Whole Region
Performance Ratio
Applications
Open Problems
Cross-References
Recommended Reading
Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Open Problems
Cross-References
Recommended Reading
Dynamic Approximate-APSP
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Approaches
Key Results
Shortcut Edges
Open Problems
Cross-References
Recommended Reading
Dynamic Trees
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Path Decomposition
Tree Contraction
Linearization
Lower Bounds
Applications
Experimental Results
Cross-References
Recommended Reading
E
Edit Distance Under Block Operations
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Exact Computation of the Standard and Permutation Edit Distance
Approximate Computation of the Standard Edit Distance
Approximate Computation of Edit Distances Involving Block Edits
Applications
Open Problems
Cross-References
Recommended Reading
Efficient Decodable Group Testing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Minimize Number of Tests
Efficient Decoding
Applications
Open Problems
Recommended Reading
Efficient Dominating and Edge Dominating Sets for Graphs and Hypergraphs
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
ED for Graphs
EED for Graphs
XC, ED, and EED for Hypergraphs
Recommended Reading
Efficient Methods for Multiple Sequence Alignment with Guaranteed Error Bounds
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notations and Definitions
The Sum of Pairs (SP) Measure
The Tree Alignment (TA) Measure
Key Results
Applications
Open Problems
Experimental Results
Data Sets
Cross-References
Recommended Reading
Efficient Polynomial Time Approximation Scheme for Scheduling Jobs on Uniform Processors
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Known Techniques
New Results
Integer Linear Programming and Grouping Techniques
Algorithm Avoiding the MILP
Lower Bounds
Open Problems
Experimental Results
Recommended Reading
Engineering Algorithms for Computational Biology
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Phylogeny Reconstruction
Experimental Results
Cross-References
Recommended Reading
Engineering Algorithms for Large Network Applications
Years and Authors of Summarized Original Work
Problem Definition
Key Results
First Approach: Graph Annotation
Second Approach: Auxiliary Graph
Modeling Issues
Applications
Open Problems
Experimental Results
Data Sets
URL to Code
Cross-References
Recommended Reading
Engineering Geometric Algorithms
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Decomposition
Point Location
Applications
Triangulations
Arrangements
Open Problems
URL to Code
Cross-References
Recommended Reading
Enumeration of Non-crossing Geometric Graphs
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Enumeration of Triangulations
Enumeration of Non-crossing Geometric Graphs
Enumeration of Non-crossing Perfect Matchings
Open Problems
Cross-References
Recommended Reading
Enumeration of Paths, Cycles, and Spanning Trees
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Path and Cycles
Spanning Trees
Applications
Recommended Reading
Equivalence Between Priority Queues and Sorting
Keywords
Synonyms
Years and Authors of Summarized Original Work
Problem Definition
Background
Key Results
The Reduction in Theorem 1
The Reduction in Theorem 2
Further Improvement
Applications
Open Problems
Cross-References
Recommended Reading
Estimating Simple Graph Parameters in Sublinear Time
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Estimating the Average Distance
Comments for the Recommended Reading
Recommended Reading
Euclidean Traveling Salesman Problem
Keywords
Years and Authors of Summarized Original Work
Problem Definition
The Euclidean Traveling Salesman Problem (TSP)
Related Work
Key Results
Applications
Euclidean Minimum Steiner Tree
Euclidean k-median
Euclidean k-TSP
Euclidean k-MST
Euclidean Minimum-Cost k-Connected Subgraph
Extensions to Planar Graphs and Metric Spaces with Bounded Doubling Dimension
Open Problems
Experimental Results
URLs to Code and Data Sets
Cross-References
Recommended Reading
Exact Algorithms and Strong Exponential Time Hypothesis
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Lower Bounds on General Problems
k-Dominating Set
2Sat+2Clauses
HornSat+kClauses
3-Party Set Disjointness
k-SUM
k-Hitting Set
k-Set Splitting
k-NAE-Sat
c-VSP-Circuit-SAT
Problems Parameterized by Treewidth
Independent Set
Dominating Set
Max Cut
Odd Cycle Transversal
Graph Coloring
Partition Into Triangles
Showing Difficulty Via Set Cover
Steiner Tree
Connected Vertex Cover
Set Partitioning
Subset Sum
Open Problems
Cross-References
Recommended Reading
Exact Algorithms and Time/Space Tradeoffs
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
A Space Efficient Algorithm for Subset Sum
The Discrete Fourier Transform
Using the Discrete Fourier Transform for Subset Sum
Evaluating Equation 2 with Finite Precision
A Generic Framework
Applications
Cross-References
Recommended Reading
Exact Algorithms for Bandwidth
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Bucketing
Dynamic Programming
Further Improvements
Related Work
Open Problems
Cross-References
Recommended Reading
Exact Algorithms for Dominating Set
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Known Results
Exact Exponential Algorithms
Key Results
Branch and Reduce and Measure and Conquer
Getting Faster MDS Algorithms
Counting Dominating Sets
Applications
Open Problems
Cross-References
Recommended Reading
Exact Algorithms for General CNF SAT
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notation
Key Results
Bounds for β and γ
General Approach and a Bound for β
Simplification Rules
A Bound for γ
A Bound for α
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Exact Algorithms for Induced Subgraph Problems
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Branching on Forbidden Induced Subgraphs
Exploiting a Large Substructure
Potential Maximal Cliques
Recommended Reading
Exact Algorithms for k SAT Based on Local Search
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Exact Algorithms for Maximum Independent Set
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Bounding the Size of the Search Tree
Refined Branching Rules
Measure and Conquer
Memorization
Cross-References
Recommended Reading
Exact Algorithms for Maximum Two-Satisfiability
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notation
Key Result
Key Idea
Main Algorithm
Applications
Open Problems
Cross-References
Recommended Reading
Exact Algorithms for Treewidth
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Exact Algorithms on Graphs of Bounded Average Degree
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Bounded Degree Graphs
Traveling Salesman Problem
Chromatic Number
Bounded Average Degree
Generalizing Algorithms for Bounded Degree Graphs
Counting Perfect Matchings in Bipartite Graphs
Cross-References
Recommended Reading
Exact Graph Coloring Using Inclusion-Exclusion
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Recommended Reading
Exact Quantum Algorithms
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Early Results
Recent Developments
Methods
Experimental Results
Cross-References
Recommended Reading
Experimental Implementation of Tile Assembly
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Experimental Results
Cross-References
Recommended Reading
Experimental Methods for Algorithm Analysis
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Data Sets
URL to Code
Recommended Reading
Exponential Lower Bounds for k-SAT Algorithms
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
The PPSZ Algorithm
A Very Brief Sketch of the Analysis of PPSZ
Hard Instances for the PPSZ Algorithm
The Probabilistic Construction
Open Problems
Cross-References
Recommended Reading
External Sorting and Permuting
Keywords
Synonyms
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Sorting by Distribution
Sorting by Merging
Handling Duplicates: Bundle Sorting
Permuting and Transposition
Fast Fourier Transform and Permutation Networks
Lower Bounds on I/O
Applications
Open Problems
URL to Code
Cross-References
Recommended Reading
F
Facility Location
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Variants and Related Problems
Key Results
The Algorithms of Shmoys, Tardos, and Aardal
UFL
max-UFL
k-Median, k-Center
Capacitated Facility Location
k-Level Problem
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Failure Detectors
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
The Failure Detector Abstraction
Consensus Algorithms
Failure Detector Reductions
Applications
A Practical Perspective
A Theoretical Perspective
Open Problems
Cross-References
Recommended Reading
False-Name-Proof Auction
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Fast Minimal Triangulation
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Fast Subset Convolution
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Problem (Subset Convolution)
Key Results
Fast Evaluation via the Union Product
Extensions and Variations
Applications
Boolean Subset Convolution
Min-Sum Subset Convolution
Cross-References
Recommended Reading
Faster Deterministic Fully-Dynamic Graph Connectivity
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
A Simple Data Structure
A Faster Data Structure
Open Problems
Recommended Reading
Fault-Tolerant Connected Dominating Set
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Mathematical Formulation
Key Results
Constant Approximation for 3-Connected m-Dominating Set
Core Idea
Brief Description
Open Problems
Experimental Results
Cross-References
Recommended Reading
Fault-Tolerant Quantum Computation
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Experimental Results
URL to Code
Cross-References
Recommended Readings
Finding Topological Subgraphs
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Previous Work
Key Results
Outline of the Proof
G has Bounded Tree-Width
G has Large Tree-Width, but no Large Clique Minor
G has a Large Clique Minor
Applications
Recommended Readings
First Fit Algorithm for Bin Packing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Applications
Key Results
Methods
New Lower Bound Construction
Open Problems
Cross-References
Recommended Readings
Fixed-Parameter Approximability and Hardness
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Our Subject
Our Complexity Assumption
Key Results
Other Parameters
Fixed-Parameter Inapproximability
Cross-References
Recommended Readings
Floorplan and Placement
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notations
Key Results
Minimum Area Placement from SP = (Γ+, Γ-)
Applications
Open Problems
BSG
SP or SS
Open Problem (SP)
Cross-References
Recommended Readings
Flow Time Minimization
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Input
Goal
Off-line versus On-line
Further Assumptions in the On-line Case
Performance Metric
Preemption
Key Results
Algorithms
Complexity
Extensions
Applications
Open Problems
Cross-References
Recommended Reading
Force-Directed Graph Drawing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Fixed Boundary
Orthogonality
Distances
Repulsion
Recommended Reading
FPGA Technology Mapping
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Introduction
Data Representation and Preliminaries
Problem Formulation
Key Results
Structure of Depth-Optimal K-Covers
Minimum Height K-Feasible Cut Computation
K-Cover Construction
Applications
Complicated Delay Models
Complicated Architectures
Multiple Optimization Objectives
Integration with Other Optimizations
Cross-References
Recommended Reading
Fractional Packing and Covering Problems
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Definitions and Notation
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Frequent Graph Mining
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
gSpan
Gaston
URLs to Code and Data Sets
Cross-References
Recommended Reading
Frequent Pattern Mining
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Algorithms
Apriori
Backtrack Algorithm
Database Reduction
Delivery
Generalizations and Extensions
Frequent Sequence Mining
Frequent Ordered Tree Mining
Recommended Reading
Fully Dynamic All Pairs Shortest Paths
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Experimental Results
Data Sets
Cross-References
Recommended Reading
Fully Dynamic Connectivity
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Open Problems
Applications
URL to Code
Cross-References
Recommended Reading
Fully Dynamic Connectivity: Upper and Lower Bounds
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Experimental Results
Data Sets
Cross-References
Recommended Reading
Fully Dynamic Higher Connectivity
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Fully Dynamic Higher Connectivity for Planar Graphs
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Fully Dynamic Minimum Spanning Trees
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Experimental Results
Data Sets
Cross-References
Recommended Reading
Fully Dynamic Planarity Testing
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Fully Dynamic Transitive Closure
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
G
Gate Sizing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
General Equilibrium
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Market Model
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Generalized Steiner Network
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Techniques
Applications
Open Problems
Cross-References
Recommended Reading
Generalized Two-Server Problem
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Online Routing Problems
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Generalized Vickrey Auction
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Geographic Routing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Geometric Approaches to Answering Queries
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Query Release
Marginal Queries
Matrix Notation
Key Results
The Sensitivity Polytope
The Generalized Gaussian Mechanism
The Projection Mechanism
Running in Time Sublinear in |X|
Optimal Error for Small Databases
Recommended Reading
Geometric Dilation of Geometric Networks
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Geometric Object Enumeration
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Enumeration of All Floor Plans
Enumeration of Triangulations
Cross-References
Recommended Reading
Geometric Shortest Paths in the Plane
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Visibility Graph Algorithms
Continuous Dijkstra Algorithms
Continuous Dijkstra with Sector Propagation Queries
Continuous Dijkstra in a Conforming Subdivision
Extensions
Cross-References
Recommended Reading
Geometric Spanners
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Spanners of Points in Euclidean Space
The Θ-Graph
Skip-List Spanners
Gap Greedy
The WSPD Graph
The Greedy Spanner
The Transformation Technique
Fault-Tolerant Spanners
Spanners Among Obstacles
Dynamic and Kinetic Spanners
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Global Minimum Cuts in Surface-Embedded Graphs
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Problem 1 (Minimum (s,t)-Cut)
Problem 2 (Global Minimum Cut)
Key Results
Topological Background
Crossing Sequences
Z2-Homology Cover
Global Minimum Cuts
Open Problems
Cross-References
Recommended Reading
Global Routing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Cross-References
Recommended Reading
Gomory-Hu Trees
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Experimental Results
Recommended Reading
Grammar Compression
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Hardness
Algorithms for Finding Small Grammars
Heuristics
Approximation Algorithms
Decompression
URLs to Code and Data Sets
Cross-References
Recommended Reading
Graph Bandwidth
Keywords
Years and Authors of Summarized Original Work
Problem Definition
The Local Density
Key Results
Volume-Respecting Embeddings
Applications
Open Problems
Recommended Reading
Graph Coloring
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Vector Coloring of Graphs
Key Results
Applications
Open Problems
Recommended Reading
Graph Connectivity
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Lower Bounds for k-Connected Spanning Subgraphs
DFS-Based Approaches
Matching-Based Approaches
1+1k Algorithm for k-VCSS
1+2k+1 Algorithm for k-ECSS
Better Algorithms for Small k
Applications
Recommended Reading
Graph Isomorphism
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Formal Description
Canonical Labeling
Key Results
Applications
Isomorphism of Edge-Colored Graphs
Isomorphism of Hypergraphs and Designs
Other Examples
Experimental Results
URL to Code
Cross-References
Recommended Reading
Graph Sketching
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Linear Sketches
Key Results
Connectivity
Basic Non-sketch Algorithm
Designing the Sketches
Emulation Basic Algorithm via Sketches
Extensions and Further Work
Cross-References
Recommended Reading
Greedy Approximation Algorithms
Keywords
Problem Definition
Key Results
The Role of Submodularity
Greedy Algorithm B
Giving Up Submodularity
Applications
Open Problems
Cross-References
Acknowledgments
Recommended Reading
Greedy Set-Cover Algorithms
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Other Results
Applications
Recommended Reading
H
Hamilton Cycles in Random Intersection Graphs
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Haplotype Inference on Pedigrees Without Recombinations
Keywords
Years aud Authors of Summarized Original Work
Problem Definition
Key Results
Cross-References
Recommended Reading
Hardness of Proper Learning
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notation
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Harmonic Algorithm for Online Bin Packing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Related Results
Cross-References
Recommended Reading
Hierarchical Self-Assembly
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Definitions
Power of Hierarchical Assembly Compared to Seeded
Assembly Time
Key Results
Power of Hierarchical Assembly Compared to Seeded
Assembly Time
Open Problems
Cross-References
Recommended Reading
Hierarchical Space Decompositions for Low-Density Scenes
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Binary Space Partitions
Compressed Quadtrees
Low-Density Scenes
Key Results
Binary Space Partitions
Compressed Quadtrees
Improvements and Generalizations
Cross-References
Recommended Reading
High Performance Algorithm Engineering for Large-Scale Problems
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Holant Problems
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Open Problems
Cross-References
Recommended Reading
Holographic Algorithms
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Matchgate Identities
Basis Collapse
From Art to Science
Applications
Recommended Reading
Hospitals/Residents Problem
Keywords
Synonyms
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Extensions of HR
Open Problems
URL to Code
Cross-References
Recommended Reading
Hospitals/Residents Problems with Quota Lower Bounds
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Minimizing the Number of Blocking Pairs
HR with the Option of Closing a Hospital
Classified HR
Key Results
Recommended Reading
Hub Labeling (2-Hop Labeling)
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
General Hub Labelings
Hierarchical Hub Labelings
From Orderings to Labelings
Vertex Ordering Heuristics
Label Representation and Queries
Experimental Results
Recommended Reading
Huffman Coding
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Constraints
Key Results
Example Weights
Huffman's Algorithm
Implementing Huffman's Algorithm
Nonbinary Output Alphabets
Dynamic Huffman Coding
Applications
Cross-References
Recommended Reading
I
I/O-Model
Keywords
Years and Authors of Summarized Original Work
Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Implementation Challenge for Shortest Paths
Keywords
Years and Authors of Summarized Original Work
Problem Definition
The 9th DIMACS Implementation Challenge: The Shortest Path Problem
Key Results
Applications
Open Problems
Data Sets
Experimental Results
URL to Code
Cross-References
Recommended Reading
Implementation Challenge for TSP Heuristics
Keywords
Years and Authors of Summarized Original Work
Problem Definition
URL to Code
Cross-References
Recommended Reading
Implementing Shared Registers in Asynchronous Message-Passing Systems
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Implementing a Regular Register
Implementing an Atomic Register
Applications
Open Problems
Cross-References
Recommended Reading
Incentive Compatible Selection
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Problem Description
Formal Definitions
Notations
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Independent Sets in Random Intersection Graphs
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Other Related Work
Open Problems
Cross-References
Recommended Reading
Indexed Approximate String Matching
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Inexact Matching When k = 1
Inexact Matching When k ≥2
Practically Fast Inexact Matching
Applications
Open Problems
Cross-References
Recommended Reading
Indexed Regular Expression Matching
Keywords
Years and Authors of Summarized Work
Problem Definition
Notations
Key Results
Applications
Experimental Results
Cross-References
Recommended Reading
Indexed Two-Dimensional String Matching
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notations
Two-Dimensional Suffix Trees
Online Suffix Trees
Two-Dimensional Suffix Arrays
Submatrix Trees
Key Results
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Inductive Inference
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notation
Learning Models
Key Results
Accuracy and Convergence Constraints
The Impact of Accuracy and Convergence Constraints
Refutability
Learning All Recursive Functions
Applications
Open Problems
Cross-References
Recommended Reading
Influence and Profit
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Independent Cascade (IC) and Linear Threshold (LT) Models
Problem 1: Influence Maximization Problem (InfMax) [1]
Price-Related Propagation (PR) Frame
Pricing Strategies in the PR Frame
Problem 2: Balanced Influence and Profit Maximization Problem (BIPMax) [2]
Key Results
Submodularity and Monotony
Algorithm for InfMax
Algorithms for BIPMax
Determine the Seeds and Prices Under BYC
Determine the Seeds and Prices Under PAP
Cross-References
Recommended Reading
Influence Maximization
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Influence Diffusion
Problem (Influence Maximization)
Activation Models
Key Results
Greedy Algorithm
Inapproximation Results
Degree-Bounded Graphs
Applications
Cross-Reference
Recommended Reading
Intersections of Inverted Lists
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Objective
Design Choices
Variants
Key Results
Multi-list Processing
Uncompressed Lists
Compressed Lists
List Indexes
Bitvectors
Other Approaches
Ranking
Reordering
Applications
Open Problems
Experimental Results
URLs to Code and Datasets
Cross-References
Recommended Reading
Intrinsic Universality in Self-Assembly
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Simulation and Intrinsic Universality
Key Results
The Abstract Tile Assembly Model Is Intrinsically Universal
Noncooperative Assembly Is Weaker than Cooperative Assembly
One Tile to Rule Them All
Two Hands
Open Problems
Cross-References
Acknowledgments
Recommended Reading
J
Jamming-Resistant MAC Protocols for Wireless Networks
Keywords
Years and Authors of Summarized Original Work
Motivation
Problem Definition
Key Results
Applications
Open Problems
Experimental Results
Recommended Reading
K
k-Best Enumeration
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Cross-References
Recommended Reading
Kernelization, Bidimensionality and Kernels
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Kernelization
Graph Classes
CMSO Logic
CMSO-Optimization Problems
Bidimensionality
Separability
Key Results
Cross-References
Recommended Reading
Kernelization, Constraint Satisfaction Problems Parameterized above Average
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Cross-References
Recommended Reading
Kernelization, Exponential Lower Bounds
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Compositionality
Transformations
Cross Composition
Other Models and Improvements
Problems Without Kernels
Cross-References
Recommended Reading
Kernelization, Matroid Methods
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Background on Matroids
Linearly Represented Matroids
Gammoids
Representative Sets
Closest Sets and Gammoids
Key Results
Applications
Representative Sets: Direct Usage
Indirect Usage
Further Applications
Cross-References
Recommended Reading
Kernelization, Max-Cut Above Tight Bounds
Keywords
Years and Authors of Summarized Original Work
Problem Definition
λ-Extendibility and the Poljak-Turzík Bound
Key Results
Extensions to Π-Subgraph APT
Open Problems
Cross-References
Recommended Reading
Kernelization, MaxLin Above Average
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
MaxLin2-AA
Max-r-Lin2-AA
Open Problems
Cross-References
Recommended Reading
Kernelization, Partially Polynomial Kernels
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Open Problems
Cross-References
Recommended Reading
Kernelization, Permutation CSPs Parameterized above Average
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Open Problems
Cross-References
Recommended Reading
Kernelization, Planar F-Deletion
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Tools
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Kernelization, Polynomial Lower Bounds
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Recommended Reading
Kernelization, Preprocessing for Treewidth
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Tree Decompositions and Treewidth
Parameters
Kernelization
Key Results
Open Problems
Recommended Reading
Kernelization, Turing Kernels
Keywords
Years and Authors of Summarized Original Work
Definition and Discussion
Out-Branching: Showing the Difference
Problem Definition
Key Results
Hierarchies Based on Turing Kernels
How Much Oracle Access Is Needed?
Open Problems
Cross-References
Recommended Reading
Kinetic Data Structures
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Cross-References
Recommended Reading
Knapsack
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Recommended Reading
Knowledge in Distributed Systems
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Modeling Knowledge
Common Knowledge and Coordinated Attack
The Coordinated Attack Problem
A Hierarchy of States of Knowledge and Common Knowledge
Knowledge Gain and Loss in Asynchronous Systems
Applications and Extensions
Cross-References
Recommended Reading
L
Large-Treewidth Graph Decompositions
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Erdős-Pósa-Type Results
Improved Running Times for Fixed-Parameter Tractability
Open Problems
Experimental Results
URLs to Code and Data Sets
Recommended Reading
Layout Decomposition for Multiple Patterning
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Problem: Multiple Patterning Decomposition
Key Results
Multiple Patterning Decomposition for Standard Cell Designs
Minimizing Stitches
Multiple Patterning Coloring Constraint
Applications
Open Problems
Experimental Results
URLs to Code and Data Sets
Cross-References
Recommended Reading
Layout Decomposition for Triple Patterning
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
URLs to Code and Data Sets
Cross-References
Recommended Reading
Learning Automata
Keywords
Years and Authors of Summarized Original Work
Problem Definition
The Learning Model
Multiplicity Automata
Key Results
Applications
Classes of Polynomials
Classes of Boxes
Classes of DNF Formulae
Classes of Decision Trees
Negative Results
Cross-References
Recommended Reading
Learning Constant-Depth Circuits
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Positive Results
Negative Results
Applications
Open Problems
Experimental Results
Data Sets
URL to Code
Cross-References
Recommended Reading
Learning DNF Formulas
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Learning Heavy Fourier Coefficients of Boolean Functions
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Application in Cryptography
Application in Computational Learning Theory
Cross-References
Recommended Reading
Learning Significant Fourier Coefficients over Finite Abelian Groups
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Applications in Computational Learning Theory
Applications in Coding Theory
Applications in Cryptography
Application in Algorithms
Cross-References
Recommended Reading
Learning with Malicious Noise
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Cross-References
Recommended Reading
Learning with the Aid of an Oracle
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
LEDA: a Library of Efficient Algorithms
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Experimental Results
URL to Code
Cross-References
Recommended Reading
Lempel-Ziv Compression
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
LZ78
LZ77
Compression and Decompression Complexity
Compression Effectiveness
Convergence to Empirical Entropy
Relationship to Grammar Compression
Greedy Versus Non-greedy Parsing
Applications
Pattern Matching in Compressed Space
String Alignment
Open Problems
URLs to Code and Data Sets
Cross-References
Recommended Reading
Leontief Economy Equilibrium
Keywords
Synonyms
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Cross-References
Recommended Reading
LexBFS, Structure, and Algorithms
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Terminology
Example
LexBFS
Key Results
First Example of Application
Sketch of Proof
Truemper Configurations
Speeding Up of Known Algorithms
New Algorithms
Open Problems
Recommended Reading
Linearity Testing/Testing Hadamard Codes
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Alternative Formulation
Key Results
Applications
Self-Testing/Correcting Programs
Probabilistically Checkable Proofs
The BLR Test as a Building Block
Open Problems
Cross-References
Recommended Reading
Linearizability
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notation
Key Results
The Locality Property
The Non-blocking Property
Other Correctness Properties
Applications
Open Problems
Cross-References
Recommended Reading
List Decoding near Capacity: Folded RS Codes
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Description of the Code
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
List Ranking
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
List-Ranking Algorithms in Parallel External Memory
Computing a Large Independent Set of L
Lower Bounds
Applications
Experimental Results
Cross-References
Recommended Reading
List Scheduling
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Load Balancing of Temporary Tasks
Scheduling with Release Times and Precedence Constraints
Open Problems
Cross-References
Recommended Reading
Local Alignment (with Affine Gap Weights)
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Pairwise Local Alignment Problem
Basic Step
Recursion Step
Applications
URL to Code
Recommended Reading
Local Alignment (with Concave Gap Weights)
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Problem
Key Results
Applications
Open Problem
Experimental Results
Cross-References
Recommended Reading
Local Approximation of Covering and Packing Problems
Synomyms
Years and Authors of Summarized Original Work
Problem Definition
Distributed Computation Model
Distributed Covering and Packing Problems
Bounded Independence Graphs
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Local Computation in Unstructured Radio Networks
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Recommended Reading
Local Reconstruction
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Connections with Other Models
Key Results
Monotonicity
Lipschitz Continuity
Dense Graph Properties
Connectivity Properties of Sparse Graphs
Convexity in 2, 3-Dimensions
Open Problems
The Curse of Dimensionality for Monotonicity and Lipschitz
Filters for Convexity
Filters for Properties of Bounded-Degree Graphs
Cross-References
Recommended Reading
Local Search for K-medians and Facility Location
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
k-Medians
Facility Location
Capacitated Variants
Related Algorithmic Techniques
Applications
Cross-References
Recommended Reading
Locality in Distributed Graph Algorithms
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Computational Model
Classical Tasks
Key Results
Local Algorithms
Almost Local Algorithms
Additional Results
Open Problems
Recommended Reading
Locally Decodable Codes
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notation and Formal Definition
Key Results
Low-Query Regime
High-Rate Regime
Applications
Open Problems
Recommended Reading
Locally Testable Codes
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Local Testability of Hadamard Codes
Local Testability of Reed-Muller Codes
Open Problems
Cross-References
Recommended Reading
Low Stretch Spanning Trees
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Lower Bounds Based on the Exponential Time Hypothesis: Edge Clique Cover
Keywords
Years and Authors of Summarized Original Work
The Exponential Time Hypothesis and Its Consequences
Problem Definition
Key Results
Discussion
Recommended Reading
Lower Bounds for Dynamic Connectivity
Keywords
Years and Authors of Summarized Original Work
Problem Definition
The Partial-Sums Problem
Relation to Dynamic Connectivity
Key Results
Understanding Hierarchies
Epochs
Time Hierarchies
An Optimal Epoch Construction
Technical Difficulties
Nondeterminism
Alternative Histories
Bit-Probe Complexity
Applications
Open Problems
Recommended Reading
Lower Bounds for Online Bin Packing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Open Problems
Cross-References
Recommended Reading
Lowest Common Ancestors in Trees
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
RMQ
Reducing LCA to RMQ
Reducing RMQ to LCA
An Algorithm for RMQ
LCA on Special Trees and RMQ on Special Arrays
Paths and Balanced Binary Trees
An "426830A O(n), O(1) "526930B -Time Algorithm for 1RMQ
Labeling Schemes
Succinct Representations
Cross-References
Recommended Reading
LP Based Parameterized Algorithms
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Method Description
Key Results
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
LP Decoding
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Error-Correcting Codes and Maximum-Likelihood Decoding
LP Decoding
Comparing with ML Decoding
Normal Cones and C-Symmetry
Using a Dual Witness to Prove Error Bounds
Key Results
Low-Density Parity-Check Codes
Expander Codes
Turbo Codes
Applications
Open Problems
Cross-References
Recommended Reading
M
Majority Equilibrium
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Cross-References
Recommended Reading
Manifold Reconstruction
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Cocone Complex
Čech Complex
Tangential Delaunay Complex
Implicit Function
Cross-References
Recommended Reading
Market Games and Content Distribution
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Uncoordinated Two-Sided Markets
Distributed Caching Problem
Strategic Games
Best-Response Moves
Nash Equilibria
State Graph
Price of Anarchy
Distributed Caching Games
Special Cases
Many-to-One Two-Sided Markets with Ties
Monotone and Matroid Markets
Key Results
Centralized Approximation Algorithm
Price of Anarchy
Pure Nash Equilibria: Existence and Convergence
Convergence Time to Equilibria
Applications
Open Problems
Cross-References
Recommended Reading
Matching in Dynamic Graphs
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Result
Ideas Underlying the Algorithm
The 2-level Algorithm
Handling Insertion of an Edge
Handling Deletion of an Edge
Analysis of the Algorithm
The log2 n-level Algorithm
Open Problems
Recommended Reading
Matching Market Equilibrium Algorithms
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Extensions
Cross-References
Recommended Reading
Matroids in Parameterized Complexity and Exact Algorithms
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Parameterized and Exact Algorithms
Open Problems
Cross-References
Recommended Reading
Max Cut
Keywords
Synonyms
Year and Authors of Summarized Original Work
Problem Definition
Linear Programming Relaxations
Eigenvalue Upper Bounds
Key Result
A Semidefinite Relaxation
Random-Hyperplane Rounding
Integrality Gap and Hardness
Better-than-Half Approximations Without SDPs
Applications
Cross-References
Recommended Reading
Max Leaf Spanning Tree
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Objective A: FPT Algorithms
Objective B: Polynomial-Time Preprocessingand Data-Reduction Routines
Objective C: Gradients and Solution Transformations for Local Search
Objective D: Polynomial-TimeApproximation Algorithms
Objective E: Structure To Exploitin The Ecology of Complexity
Applications
Open Problems
Branching Strategies
Turing Kernelizability
Algorithmic Forms of The Boundary Lemma Approach
Problem Annotation
Cross-References
Recommended Reading
Maximizing the Minimum Machine Load
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Approximation Algorithms
Online and Semi-online Problem
Applications
Cross-References
Recommended Reading
Maximum Agreement Subtree (of 2 Binary Trees)
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Previous Work
Our Contribution
Special Case 1
Special Case 2
Improvement 1
Improvement 2
The Multiple Degree Case
Applications
Motivation
Cross-References
Recommended Reading
Maximum Agreement Subtree (of 3 or More Trees)
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Proper Domination Relation
Applications
Cross-References
Recommended Reading
Maximum Agreement Supertree
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Maximum Cardinality Stable Matchings
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Benchmark Results
Upper Bounds: The General Case
Upper Bounds: Special Cases
Lower Bounds
Applications
Recommended Reading
Maximum Compatible Tree
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Exact Algorithms
Approximation Algorithms
Applications
Open Problems
URLs to Code and Datasets
Cross-References
Recommended Reading
Maximum Lifetime Coverage
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Formal Definition of MLCP
Key Results
Integer Linear Programming and Heuristic Algorithms Proposed by Cardei et al. ch617:cardeiinfocom
Performance-Guaranteed Approximation Algorithm Proposed by Ling et al. ch617:ling2012
Experimental Results
Recommended Reading
Maximum Matching
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Classical Approach
Algebraic Approach
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Maximum-Average Segments
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
An Extension to Multiple Segments
Applications
Open Problems
Cross-References
Recommended Reading
Maximum-Sum Segments
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
An Extension to Multiple Segments
Applications
Open Problems
Cross-References
Recommended Reading
Max-Min Allocation
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Sketch of the Techniques
Summary
Recommended Reading
Mechanism Design and Differential Privacy
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Generic Problems
Basic Differentially Private Mechanisms
Key Results
Privacy-Aware Mechanism Design
Worst-Case Privacy Model
Per-Outcome Privacy Model
Comparison with Worst-Case Privacy
Purchasing Privacy
Insensitive Valuation Model
Sensitive Value Model
Recommended Reading
Mellor-Crummey and Scott Mutual Exclusion Algorithm
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Local-Spin Algorithms and the RMRs Metric
Read-Modify-Write Operations
Key Results
The Algorithm
Cross-References
Further Reading
Recommended Reading
Memory-Constrained Algorithms
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Considerations on the Input
Considerations on the Workspace
Key Results
Selection and Sorting in Multi-pass Models
Selection
Randomized Algorithms
Improvements
Undirected Graph Connectivity in the Random Access Model
Problem Background
Reingold's Algorithm
Other Models of Note
Compressed Stack
Block Reconstruction
Cross-References
Recommended Reading
Memoryless Gathering of Mobile Robotic Sensors
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Basic Impossibility Results
Gathering with Common Coordinate Systems
Convergence and Near-Gathering
Convergence in Ssync
Convergence in Async
Near-Gathering
Open Problems
Recommended Reading
Meshing Piecewise Smooth Complexes
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
URLs to Code and Data Sets
Cross-References
Recommended Reading
Message Adversaries
Keywords
Years and Authors of Summarized Original Work
Problem Definition: The Notion of a Message Adversary
Reliable Synchronous Systems
Message Adversary
Key Results
Key Results in Synchronous Systems
The Spanning Tree Adversary
Consensus in the Presence of Message Adversaries
Impossibility Agreement-Related Results
d-Solo Executions
Key Results in Asynchronous Systems
Applications
Cross-References
Recommended Reading
Metric TSP
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Experimental Results
Data Sets
Cross-References
Recommended Reading
Metrical Task Systems
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notation
Key Results*-1pc
Applications
Open Problems
Cross-References
Recommended Reading
Min-Hash Sketches
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Set Operations
Queries
Key Results
Structure
Rank Distribution
Streaming: Number of Updates
Inserting an Element
Merging
Estimators
Applications
Extensions
Weighted Elements
Hash Functions
Cross-References
Recommended Reading
Minimal Dominating Set Enumeration
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Open Problems
Cross-References
Recommended Reading
Minimal Perfect Hash Functions
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Problem Formulation
Key Results
From a PHF to a MPHF
The Hypergraph-Based Construction
The ``Hash, Displace, and Compress'' Construction
Open Problems
URLs to Code and Data Sets
Cross-References
Recommended Reading
Minimum Bisection
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Overview
Cuts and Bisections
Balanced Cuts and Edge Separators
Key Results
Related Work
Applications
Open Problems
Cross-References
Recommended Reading
Minimum Congestion Redundant Assignments
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notations and Definitions
Key Results*-1pc
Applications
Open Problems
Cross-References
Recommended Reading
Minimum Connected Sensor Cover
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Open Problems
Cross-References
Recommended Reading
Minimum Energy Broadcasting in Wireless Geometric Networks
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Analysis
Applications
Open Problems
Cross-References
Recommended Reading
Minimum Energy Cost Broadcasting in Wireless Networks
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Minimum Flow Time
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notations
Key Results
Extensions
Applications
Open Problems
Cross-References
Recommended Reading
Minimum Geometric Spanning Trees
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Approximate and Dynamic Solutions
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Minimum k-Connected Geometric Networks
Keywords
Synonyms
Years and Authors of Summarized Original Work
Problem Definition
Notations
Related Work
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Minimum Spanning Trees
Keywords
Years and Authors of Summarized Original Work
Problem Definition
History
Related Problems
Optimality Conditions
The Generic Greedy Algorithm
Modeling MST Algorithms
Key Results
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Minimum Weight Triangulation
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
The Quasi-Greedy Triangulation Approximates the MWT
Computing the Exact Minimum Weight Triangulation
Applications
Open Problems
Experimental Results
URL to Code
Cross-References
Recommended Reading
Minimum Weighted Completion Time
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Min-Sum Set Cover and Its Generalizations
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Histogram-Based Analysis
Latency Argument-Based Analysis
LP and Randomized Rounding
Applications
Open Problems
Recommended Reading
Misra-Gries Summaries
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Preliminaries: The Majority Algorithm
Misra-Gries Summary
Applications
Experimental Results
URLs to Code and Data Sets
Cross-References
Recommended Reading
Mobile Agents and Exploration
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Mobile Agents
Network Model
Efficiency Measures for Exploration
Main Problems
Key Results
Exploration in General Graphs
Exploration in Trees
Exploration in a Geometric Setting
Rendezvous
Applications
Open Problems
Cross-References
Recommended Reading
Model Checking with Fly-Automata
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Graph Algebras and Monadic Second-Order Logic
Counting and Optimizing Automata
Edge Set Quantifications and Tree-Width
Beyond MS Logic
Open Problems
Experimental Results
Recommended Reading
Modularity Maximization in Complex Networks
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Computational Complexity
Exact Solutions
Approximation Algorithms
Modularity in Dynamic Networks
Applications
Recommended Reading
Monotone Minimal Perfect Hash Functions
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Problem Formulation
Key Results
Trivial Solution
A Constant-Time, O(n logw)-Space Solution
A O(logw)-Time, O(n loglogw)-Space Solution
Different Approaches
Open Problems
URLs to Code and Datasets
Cross-References
Recommended Reading
Monotonicity Testing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Property Testing Framework
Key Results
Sketch of the Techniques
Boolean Monotonicity Testing
Open Problems
Cross-References
Recommended Reading
Multi-armed Bandit Problem
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Definitions and Notation
Key Results
Variants
Applications
Cross-References
Recommended Reading
Multicommodity Flow, Well-linked Terminals and Routing Problems
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Generalizations and Variants
Applications
Open Problems
Cross-References
Recommended Reading
Multicut
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Multidimensional Compressed Pattern Matching
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Multidimensional String Matching
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Multilevel Feedback Queues
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notations
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Multilinear Monomial Detection
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Overview of the Algorithm
A Negative Result
A Generalization
Applications
Open Problems
Cross-References
Recommended Reading
Multiple String Matching
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Experimental Results
URLs to Code and Data Sets
Cross-References
Recommended Reading
Multiple Unit Auctions with Budget Constraint
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Cross-References
Recommended Reading
Multiplex PCR for Gap Closing (Whole-Genome Assembly)
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Recommended Reading
Multitolerance Graphs
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Efficient Algorithms
Classification of Multitolerance Graphs
Open Problems
Recommended Reading
Multiway Cut
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Previous Work
Key Results
Notation
LP-Relaxation
Rounding
Applications
Open Problems
Cross-References
Recommended Reading
Musite: Tool for Predicting Protein Phosphorylation Sites
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Machine Learning Approach
Features
Bootstrap and Aggregation
Cross Validation
Musite as a Toolkit
Applications
Open Problems
URLs to Code
Cross-References
Recommended Reading
N
Nash Equilibria and Dominant Strategies in Routing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notations
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Nearest Neighbor Interchange and Related Distances
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Unweighted Trees
Weighted Trees
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Negative Cycles in Weighted Digraphs
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Experimental Results
Data Sets
URL to Code
Cross-References
Recommended Reading
Network Creation Games
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notation
Key Results
Techniques
Recommended Reading
Non-approximability of Bimatrix Nash Equilibria
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Non-shared Edges
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Non-shared Edge Distance Problem
All-Pairs Non-shared Edge Distance Problem
Extension
General Non-shared Edge Distance Problem
Key Results
Applications
Recommended Reading
Nowhere Crownful Classes of Directed Graphs
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Nucleolus
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
O
O(log log
n)-Competitive Binary Search Tree
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Extensions and Promising Research Directions
Cross-References
Recommended Reading
Recommended Reading
Oblivious Routing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notations
Key Results
Techniques
Applications
Cross-References
Recommended Reading
Oblivious Subspace Embeddings
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Constructing OSEs
Applying OSEs
Least Squares Regression
Low-Rank Approximation
Other Applications
Recommended Reading
Obstacle Avoidance Algorithms in Wireless Sensor Networks
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Geographic Routing
The Power of Simple Geographic Routing
Problem Statement
Key Results
Basic Idea of the Algorithm
Inertia Mode
Rescue Mode
Main Findings
Applications
Replacement for Greedy Forwarding
Wireless Sensor Networks with Large Obstacles
Dynamic Networks
Open Problems
Cross-References
Recommended Reading
Online Interval Coloring
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Online Learning and Optimization
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Online Convex Programming
Key Results
Cross-References
Recommended Reading
Online List Update
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Randomized Algorithms
Locality of Reference
Applications
Open Problems
Cross-References
Recommended Reading
Online Load Balancing of Temporary Tasks
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Identical Machines
Uniformly Related Machines
Restricted Assignment
Unrelated Machines
Applications
Open Problems
Cross-References
Recommended Reading
Online Node-Weighted Problems
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Online Paging and Caching
Keywords
Years and Authors of Summarized Original Work
Synonyms
Problem Definition
Key Results
Paging
Weighted Caching
File Caching
Other Theoretical Models
Analyses of Deterministic Algorithms
Extension to File Caching
Analysis of the Randomized Marking Algorithm.
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Online Preemptive Scheduling on Parallel Machines
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Key Techniques
Semi-online Scheduling
Small Number of Machines
Open Problems
Cross-References
Recommended Reading
Optimal Crowdsourcing Contests
Keywords
Years and Authors of Summarized Original Work
Problem Definition
The Questions
The Model
Bayesian Nash Equilibrium
Key Results
Rank-Based-Reward Contests
Optimal Symmetric Contest
Utilization Ratio of Crowdsourcing
Related Work
Open Problems
Multi-round Contests
Cross-References
Recommended Reading
Optimal Probabilistic Synchronous Byzantine Agreement
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notations
System Model
Key Results
Applications
Cross-References
Recommended Reading
Optimal Stable Marriage
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Optimal Triangulation
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
The Edge-Flip Approach
The Edge-Insertion Approach
The Subgraph Approach
Applications
Open Problems
URLs to Code and Data Sets
Cross-References
Recommended Reading
Optimal Two-Level Boolean Minimization
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Karnaugh Maps
The Quine–McCluskey Algorithm
Applications
Cross-References
Recommended Reading
Orienteering Problems
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Undirected Graphs
Directed Graphs
Orienteering with Time Windows
Open Problems
Recommended Reading
Orthogonal Range Searching on Discrete Grids
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Orthogonal Range Reporting
Two Dimensions
Three Dimensions
Multi-dimensional Queries
Emptiness Queries and One-Reporting Queries
Two-Dimensional Range Successor and Sorted Range Reporting Queries
Orthogonal Range Counting
Open Problems
Cross-References
Recommended Reading
P
P2P
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Unstructured Overlays
Structured Overlays Without Locality Awareness
Chord
Constant Per-Node State
Content Addressable Network
Overlay Routing Inspired by “Small-World” Networks
Overlay Networks Supporting Range Queries
Summary of Non-Locality-Aware Networks
Locality Awareness
Growth-Bounded Networks
Applications
Caching
Multicast
Routing Infrastructure
Collaborative Content Delivery
Cross-References
Recommended Reading
PAC Learning
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Cross-References
Recommended Reading
Packet Routing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Network Emulations
Job Shop Scheduling
Open Problems
Recommended Reading
Packet Switching in Multi-queue Switches
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Unit Value Packets
Deterministic Algorithms
Randomized Algorithms
Arbitrary Value Packets
Applications
Open Problems
Cross-References
Recommended Reading
Packet Switching in Single Buffer
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
PageRank Algorithm
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Linear Algebra-Based Definition
Random Surfer Model
Applications
Recommended Reading
Parallel Algorithms for Two Processors Precedence Constraint Scheduling
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Preliminaries
Auxiliary Problems
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Parallel Connectivity and Minimum Spanning Trees
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Cross-References
Recommended Reading
Parameterization in Computational Social Choice
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Open Problems
Recommended Reading
Parameterized Algorithms for Drawing Graphs
Years and Authors of Summarized Original Work
Problem Definition
Notations
Key Results
Applications
Open Problems
Experimental Results
URL to Code
Cross-References
Recommended Reading
Parameterized Pattern Matching
Years and Authors of Summarized Work
Problem Definition
Key Results
Parameterized Suffix Trees
More Methods for Parameterized Matching
Two-Dimensional Parameterized Matching
Approximate Parameterized Matching
Applications
Cross-References
Recommended Reading
Parameterized SAT
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Satisfiability Parameters Based on Graph Invariants
Satisfiability Parameters Based on Backdoor Sets
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Parity Games
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Algorithms for Parity Games
Applications
Parity Games for Model Checking
Open Problems
Cross-References
Recommended Reading
Pattern Matching on Compressed Text
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Collage Systems
Key Results
Theoretical Aspect
Practical Aspect
Cross-References
Recommended Reading
Patterned Self-Assembly Tile Set Synthesis
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Open Problems
URLs to Code and Data Sets
Cross-References
Recommended Reading
Peptide De Novo Sequencing with MS/MS
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
URL to Code
Recommended Reading
Perceptron Algorithm
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Cross-References
Recommended Reading
Perfect Phylogeny (Bounded Number of States)
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Perfect Phylogeny Haplotyping
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Perfect Phylogeny Haplotyping Problem (PPH)
Key Results
Applications
Open Problems
Experimental Results
Data Sets
URL to Code
Cross-References
Recommended Reading
Performance-Driven Clustering
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Experimental Results
Cross-References
Recommended Reading
Permutation Enumeration
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Permutation Enumeration
Efficiency of Enumeration Algorithms
Key Results
Enumeration by Partition Search
Enumeration by Gray Code
Enumeration by Reverse Search
Recommended Reading
Phylogenetic Tree Construction from a Distance Matrix
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Cross-References
Recommended Reading
Planar Directed k-Vertex-Disjoint Paths Problem
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Key Techniques for Planar Directed Graphs
The Schrijver's Algorithm
The Fixed-Parameter Algorithm
Cross-References
Recommended Reading
Planar Geometric Spanners
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Planar Maximum Flow – Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Near-Linear Time Algorithm
Applications
Recommended Reading
Planar Maximum s-t Flow
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
st-Planar Graphs
Undirected Planar Graphs
Directed Planar Graphs
Leftmost-Path Algorithm
Applications
Open Problems
Experimental Results
URLs to Code and Data Sets
Cross-References
Recommended Reading
Planarisation and Crossing Minimisation
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Planarization Algorithms
Exact Approaches
Open Problems
URLs to Code and Data Sets
Recommended Reading
Planarity Testing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
URL to Code
Cross-References
Recommended Reading
Point Location
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Walking in a Triangulation
Trapezoidal Decomposition
Hierarchical Triangulation
Hybrid and Refined Approaches
Experimental Results
Cross-References
Recommended Reading
Point Pattern Matching
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Cross-References
Recommended Reading
Polygon Triangulation
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Polygon Triangulation in o(Nlog N) Time
Polygon Triangulation via Trapezoidation
Polygon Triangulation in Linear Time
Randomized Polygon Triangulation in Expected Linear Time
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Position Auction
Keywords
Years and Authors of Summarized Original Work
Problem Definition
The Model and Its Notations
Definitions
Key Results
Facts of NE and SNE
A Sufficient and Necessary Condition of the Existence of a Pure Strategy Nash Equilibrium in the Position Auction Game
Applications
Cross-References
Recommended Reading
Power Grid Analysis
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Hierarchy-Based Solvers
Multigrid-Based Solvers
Random Walk-Based Solvers
Applications
Experimental Results
URLs to Code and Data Sets
Recommended Reading
Predecessor Search
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Upper Bounds
Lower Bounds
Bucketing
Applications
Open Problems
Cross-References
Recommended Reading
Predecessor Search, String Algorithms and Data Structures
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Useful Concepts
Balanced Binary Search Tree
Trie
Key Results
Van Emde Boas
Searching a Compacted Trie (Fusion Trees)
Beame and Fich
Exponential Search Trees
Deterministic Dynamic Bounds
Optimal Static Bounds
Optimal Randomized Dynamic Bounds
Applications
Open Problems
Cross-References
Recommended Reading
Price of Anarchy
Keywords
Synonyms
Years and Authors of Summarized Original Work
Problem Definition
Notation
Key Results
Maximum Social Cost
Average Social Cost: Total Latency
Applications
Cross-References
Recommended Reading
Price of Anarchy for Machines Models
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Early Work
Tight Bounds for the Price of Anarchy
Applications
Open Problems
Experimental Results
URLs to Code and Data Sets
Cross-References
Recommended Reading
Privacy Preserving Auction
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Objective 1: Maximizing Social Welfare
Objective 2: Incentive Compatibility
Objective 3: Protecting Agents' Privacy
Related Work
Key Results
Social Choice Problems
Resource Allocation Problems
Open Problems
Cross-References
Recommended Reading
Private Spectral Analysis
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Approximation Guarantee
Principal Angle
Expressed Variance
Privacy Guarantee
Key Results
Noisy Power Method
Gaussian Mechanism
Applications
Principal Component Analysis
Low-Rank Approximation
Open Problems
Recommended Reading
Probabilistic Data Forwarding in Wireless Sensor Networks
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Wireless Sensor Networks
A Simple Model
Key Results
The Basic Idea
The PFR Protocol
Phase 1: The “Front” Creation Phase
Phase 2: The Probabilistic Forwarding Phase
The φ-calculation Subprotocol (see Fig4)
Performance Properties of PFR
The Correctness of PFR
The Energy Efficiency of PFR
The Robustness of PFR
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Probe Selection
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Recommended Reading
Prophet Inequality and Online Auctions
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Different Variants
Key Results
Applications
Cross-Reference
Recommended Reading
Q
Quadtrees and Morton Indexing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
The Complexity of Quadtrees for Points in the Plane
The Complexity of Quadtrees for Line Segments in the Plane
Quadtrees and Morton Indexing
Key Results
Point Quadtrees
PM Quadtrees
Star-Quadtrees
Guard-Quadtrees
K-Quadtrees
Datasets
Experimental Results
Extensions
Recommended Reading
Quantification of Regulation in Networks with Positive and Negative Interaction Weights
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Recommended Reading
Quantum Algorithm for Element Distinctness
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Element Distinctness: Summary of Results
Element Distinctness: The Methods
Generalization to Arbitrary Markov Chains
Learning Graphs
Applications
Open Problems
Cross-References
Recommended Reading
Quantum Algorithm for Factoring
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Quantum Algorithm for Finding Triangles
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
An O(n+nm) Algorithm Using Amplitude Amplification
An O(n10/7) Algorithm Using Amplitude Amplification
An O(n13/10) Algorithm Using Quantum Walks
An O(n35/27) Algorithm Using Learning Graphs
An O(n9/7) Algorithm Using Learning Graphs
An O(n5/4) Algorithm Using Quantum Walks
Cross-References
Recommended Reading
Quantum Algorithm for Search on Grids
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Early Results
Quantum Walks
Further Developments
Applications
Cross-References
Recommended Reading
Quantum Algorithm for Solving Pell's Equation
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Quantum Algorithm for the Collision Problem
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Recommended Reading
Quantum Algorithm for the Discrete Logarithm Problem
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Description of the Discrete Logarithm Algorithm
Generalizations of the Discrete Logarithm Algorithm
Applications
Cross-References
Recommended Reading
Quantum Algorithm for the Parity Problem
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Cross-References
Recommended Reading
Quantum Algorithms for Class Group of a Number Field
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Quantum Algorithms for Graph Connectivity
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Previous Algorithm
Main Algorithm
Applications
Cross-References
Recommended Reading
Quantum Algorithms for Matrix Multiplication and Product Verification
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Matrix Product Verification over Rings
Matrix Multiplication over Rings
Boolean Matrix Product Verification
Boolean Matrix Multiplication
Matrix Multiplication over Other Semirings
Open Problems
Cross-References
Recommended Reading
Quantum Algorithms for Simulated Annealing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Problem
Key Results
Quantum Walks for QSA
Evolution Randomization and QSA Implementation
Analytical Properties of W
Applications
Open Problems
Cross-References
Recommended Reading
Quantum Algorithms for Systems of Linear Equations
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Quantum Algorithm for Linear Systems
Hardness Results and Comparison to Classical Algorithms
Applications and Extensions
Machine Learning
Differential Equations
Boundary-Value Problems
Cross-References
Recommended Reading
Quantum Analogues of Markov Chains
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Spatial Search and Walk Processes
The Quantum Walk Algorithm
Key Results
Walk Definitions
Hitting Time
Element Distinctness
General Markov Chains
Subsequent Developments
Applications
Triangle Finding
Matrix Product Verification and Matrix Multiplication
Group Commutativity Testing
Forbidden Subgraph Property
3-Distinctness
Open Problems
Search Problem
Sampling Problem
Cross-References
Recommended Reading
Quantum Approximation of the Jones Polynomial
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Understanding the Algorithm
Applications
Open Problems
Cross-References
Recommended Reading
Quantum Dense Coding
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Experimental Results
Cross-References
Recommended Reading
Quantum Error Correction
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Discretization of Noise
Syndrome Decoding and the Need for Fresh Ancillas
Conditions for General Quantum Codes
Constructing Quantum Codes
Asymptotically Good Codes
Applications
Open Problems
Experimental Results
Data Sets
URL to Code
Cross-References
Recommended Reading
Quantum Key Distribution
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Protocols
Key Rate as a Function of Robustness and Security
Security Against Individual Attacks
Security Against Collective Attacks
Security Against General Attacks
Applications
Experimental Results
Cross-References
Recommended Reading
Quantum Search
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Brief Description
Formal Construction
Key Results
Applications
NP-Complete Problems
Quantum Counting
Element Distinctness
Distributed Search
Fixed-Point Search
Spatial Search
Markov Chain Evolution
Recursive Search
Open Problems
Hamiltonian Evolution
Molecular Biology
Ordered Search
Search with Additional Structure
Perspective
Cross-References
Recommended Reading
Query Release via Online Learning
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Answering Many Queries via No-Regret Learning
Computational Complexity and Optimality
Faster Algorithms for Marginal Queries via Efficient Learning
Recommended Reading
Quorums
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Access Protocol
Key Results
Voting and Related Notions
Measures
Load
Availability
The Load and Availability of Quorum Systems
Byzantine Quorum Systems
Masking quorum system
Probabilistic Quorum Systems
Applications
Cross-References
Recommended Reading
R
Radiocoloring in Planar Graphs
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Cross-References
Recommended Reading
Random Planted 3-SAT
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notation
Distributions
Key Results
Applications
Open Problems
Data Sets
URL to Code
Recommended Reading
Randomization in Distributed Computing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Consensus Problems
Wait-Free
Multi-writer Multi-reader Register
The Adversary
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Randomized Broadcasting in Radio Networks
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Randomized Protocols
The Procedure Decay
The Broadcast Protocol
Additional Properties of the Broadcast Protocol
A Lower Bound on Deterministic Algorithms
Applications
Cross-References
Recommended Reading
Randomized Contraction
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
High-Level Intuition
Recursive Understanding
High-Connectivity Phase
Related Work
Recommended Reading
Randomized Energy Balance Algorithms in Sensor Networks
Keywords
Years and Authors of Summarized
OriginalWork
ProblemDefinition
Key Results
Applications
Cross-References
Recommended Reading
Randomized Gossiping in Radio Networks
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Recommended Reading
Randomized Minimum Spanning Tree
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Background
Key Results
Further Comments
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Randomized Parallel Approximations to Max Flow
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Maximum Flows and Matchings
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Randomized Rounding
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Randomized Searching on Rays or the Line
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notation
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Randomized Self-Assembly
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Definitions
Problems
Key Results
Open Problems
Cross-References
Recommended Reading
Range Searching
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Orthogonal Range Searching
Simplex Range Searching
Approximate Range Searching
Cross-References
Recommended Reading
Rank and Select Operations on Bit Strings
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Memory Usage Models
Models of Computation
Key Results
Relation to Predecessor Search
Reductions
Succinct Indices for Bit Vectors
Bit Vectors in the Unrestricted Model
Applications
Experimental Results
Cross-References
Recommended Reading
Rank and Select Operations on Sequences
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Dynamic Sequences
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Ranked Matching
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notations and Definitions
Key Results
Techniques
Strict Instances
General Instances
Applications
Cross-References
Recommended Reading
Rate-Monotonic Scheduling
Keywords
Years and Authors of Summarized Original Work
Problem Definition
The Periodic Task Model
The Rate-monotonic Scheduling Algorithm
Key Results
Results from[11]
Results Since [11]
Applications
Open Problems
URLs to Code and Data Sets
Cross-References
Recommended Reading
Rectilinear Spanning Tree
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Experimental Results
Cross-References
Recommended Reading
Rectilinear Steiner Tree
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Experimental Results
Cross-References
Recommended Reading
Recursive Separator Decompositions for Planar Graphs
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Cross-References
Recommended Reading
Reducing Bayesian Mechanism Design to Algorithm Design
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Model
Environment
Strategic Agents
Designer
Game Theoretic Definitions
Bayesian Mechanism Design (BMeD)
Generalized Objective Optimization Problem (GOOP)
Key Results
Applications
Revenue Maximization
Job Scheduling on Unrelated Machines
Fair Allocation of Indivisible Goods
Tools for Convex Optimization
Open Problems
Recommended Reading
Registers
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Timestamp System
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Regular Expression Matching
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Finite Automata
Classical Solutions
Lazy Construction and Modules
Bit Parallelism
Filtration
Related Problems
Applications
Open Problems
Experimental Results
URLs to Code and Data Sets
Cross-References
Recommended Reading
Reinforcement Learning
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notation
Markov Decision Process
Problems Formulation
Planning
Value Iteration
Policy Iteration
Linear Programming
Learning
Q-Learning
Key Results
Applications
Open Problems
Function Approximation
Factored Markov Decision Process
Cross-References
Recommended Reading
Renaming
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Revenue Monotone Auctions
Keywords
Introduction
Related Work
Our Results
Preliminaries
Image-Text Auctions
Video-Pod Auctions
Lower Bound
Recommended Reading
Reverse Search; Enumeration Algorithms
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Introduction
Key Results
Examples
Avoiding Long Delays
Note
Recommended Reading
RNA Secondary Structure Boltzmann Distribution
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notation
Energy Model
Key Results
Applications
Open Problems
URL to Code
Cross-References
Recommended Reading
RNA Secondary Structure Prediction by Minimum Free Energy
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notation
Energy Model
Key Results
Applications
Open Problems
Experimental Results
Data Sets
URL to Code
Cross-References
Recommended Reading
RNA Secondary Structure Prediction Including Pseudoknots
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notation
Scoring Schemes
Key Results
Applications
Open Problems
Data Sets
URL to Code
Cross-References
Recommended Reading
Robotics
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Navigation and Exploration
Performance Measure, Competitive Analysis
Different Models
Key Results
Navigation
Exploration
Dependency Between Searching and Exploration
Applications
Open Problems
Cross-References
Recommended Reading
Robust Bin Packing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Techniques
Open Problems
Cross-References
Recommended Reading
Robust Geometric Computation
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notation
Key Results
Constructive Zero Bounds
Approximate Expression Evaluation
Numerical Filters
Applications
Open Problems
URL to Code
Recommended Reading
Robust Scheduling Algorithms
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Greedy Approaches
Robust Approximation Schemes
Applications
Open Problems
Cross-References
Recommended Reading
Robustness in Self-Assembly
Keywords
Years and Authors of Summarized Original Work
Robustness in Self-Assembly
KTAM
Problem Definition
Key Results
Proofreading Tilesets
Snaked Proofreading Tilesets
Recommended Reading
Routing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notations and Definitions
Key Results
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Routing in Geometric Networks
Synonyms
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Network Model
Communication Protocol
Geometric Routing
Key Results
General (Non-geometric) Networks
Open Problems
Cross-References
Recommended Reading
Routing in Road Networks with Transit Nodes
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Experimental Results
Data Sets
URL to Code
Cross-References
Recommended Reading
Routing-Cost Constrained Connected Dominating Set
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
GOC-MCDS-C: The Centralized Algorithm
GOC-MCDS-D: The Distributed Algorithm
Open Problems
Cross-References
Recommended Reading
R-Trees
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Experimental Results
Data Sets
URL to Code
Cross-References
Recommended Reading
Rumor Blocking
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Problem1 [2]
Two Influence Diffusion Models
Problem2 [8]
Independent Cascade Model
Key Results
For Problem 1
Variants of Problem 1
Selection of Fixed Number of Protectors
Protection of a Subset of Nodes
Game Theory Aspect
For Problem 2
Bond Percolation Method [7]
Estimation Method
Variants of Problem 2
Applications
Open Problems
Cross-References
Recommended Reading
S
Schedulers for Optimistic Rate Based Flow Control
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Scheduling in Data Broadcasting
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Objective
Constraints
Problem 1 (Scheduling in Data Broadcasting)
Key Results
Hardness Analysis
Randomized Algebraic Algorithm
Preliminaries
Algorithm Description
Applications
Open Problems
Experimental Results
URLs to Code and Data Sets
Cross-References
Recommended Reading
Scheduling with a Reordering Buffer
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Metric Space Generalization
Block Operation Setting
Minor Variants Found in the Literature
Key Results
The Online Problem
Deterministic Algorithms
Randomized Algorithms
Other Metric Spaces
Stochastic Inputs
The Off-Line Problem
Bicriteria Approximations
The Maximization Problem
Online Minimum Makespan Scheduling
Non-preemptive Scheduling
Job Migrations
Preemptive Scheduling
Cross-References
Recommended Reading
Secretary Problems and Online Auctions
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Optimization Angle
Mechanism Design Angle
Key Results
Optimization
Mechanism Design
Open Problems
Cross-References
Recommended Reading
Self-Assembly at Temperature 1
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Assembling Simple Shapes Efficiently
The Role of Geometry
Three-Dimensional Noncooperative Self-Assembly
Allowing Erroneous Blocking
Simulation up to Rescaling
Important Particular Cases
Applications
Open Problems
Cross-References
Recommended Reading
Self-Assembly of Fractals
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Variants
Key Results
Weak Self-Assembly
Strict Self-Assembly
Approximate Self-Assembly
Open Problems
URLs to Code and Data Sets
Cross-References
Recommended Reading
Self-Assembly of Squares and Scaled Shapes
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Abstract Tile Assembly Model
Key Results
n×n Squares
Thin Rectangles
Scaled Shapes
Open Problems
Cross-References
Recommended Reading
Self-Assembly with General Shaped Tiles
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Models
Efficient Construction
Computational Power
Applications
Open Problems
Cross-References
Recommended Reading
Selfish Bin Packing Problems
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Related Results
Cross-References
Recommended Reading
Selfish Unsplittable Flows: Algorithms for Pure Equilibria
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Selfish Behavior
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Self-Stabilization
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Complexity Metrics
Key Results
Composition
Synchronization Tasks
Graph Algorithms
Transformation
General Methods
Fault Tolerance
Applications
Cross-References
Recommended Reading
Semi-supervised Learning
Keywords
Years and Authors of Summarized Original Work
Problem Definition
A Formal Framework
Examples
Intuition
Key Results
Co-Training
Semi-supervised SVMs
Graph-Based Methods
Open Problems
Recommended Reading
Separators in Graphs
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Related Results
Implementation
Applications
Experimental Results
Cross-References
Recommended Reading
Sequence and Spatial Motif Discovery in Short Sequence Fragments
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Spatial Motifs by Permutation Model
Expectation for Interacting Residues of the Same Type
Expectation for Interacting Residues of Different Types
Significance of Spatial Motifs
Sequences of Different Lengths
Sequence Motifs by Permutation Model
Expectation of XYk and XXk Two-Residue Motifs
Significance of XYk and XXk Two-Residue Sequence Motifs
Propensity of Multi-residue Sequence Motifs
Remark
Spatial Motifs by Positional Null Model
Expectation and Significance of Interacting Residue Pairs
Expectation and Significance of Sequence Motifs
Applications
Open Problems
Recommended Reading
Sequential Circuit Technology Mapping
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Cut Enumeration
Label Computation
Mapping Solution Generation
Applications
Cross-References
Recommended Reading
Set Agreement
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Short History
Definition
The Trivial Case
Key Results
Key Results in Synchronous Systems
The Synchronous Model
Main Results
Other Failure Models
Key Results in Asynchronous Systems
Impossibility
Circumventing the Impossibility
Applications
Cross-References
Recommended Reading
Set Cover with Almost Consecutive Ones
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notation
Key Results
Data Reduction Rules
Algorithms
Applications
Experimental Results
Cross-References
Recommended Reading
Shadowless Solutions for Fixed-Parameter Tractability of Directed Graphs
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Directed Multiway Cut
Directed Subset Feedback Vertex Set
Open Problems
Directed Multicut
Directed Odd Cycle Transversal
Cross-References
Recommended Reading
Shortest Elapsed Time First Scheduling
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notations
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Shortest Paths Approaches for Timetable Information
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Modeling
Algorithmic Models
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Shortest Paths in Planar Graphs with Negative Weight Edges
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notations
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Shortest Vector Problem
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
URL to Code
Cross-References
Recommended Reading
Similarity Between Compressed Strings
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Run-Length Encoding
LZ Compression
Block Computation
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Simple Algorithms for Spanners in Weighted Graphs
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Algorithm I
Algorithm II
Computing a 3-Spanner in Linear Time
Other Related Works
Additive Spanners
(α,β)-Spanner
Applications
Open Problems
Recommended Reading
Simpler Approximation for Stable Marriage
Keywords
Years and Authors of Summarized Original Work
Introduction
Problem Definition
Key Results
Algorithm
Preliminary Definitions and Concepts for the Algorithm
The Algorithm
Running Time, Locality
Cross-References
Recommended Reading
Single and Multiple Buffer Processing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
General Model Description
Competitive Analysis
Key Results
Uniform Processing, Uniform Value, Shared Memory Switch
Non-Push-Out Policies
Push-Out Policies
Uniform Processing, Uniform Value, Multiple Separated Queues
Uniform Processing, Variable Values, Single Queue
Non-Push-Out Policies
Push-Out Policies
Uniform Processing, Variable Values, Multiple Separated Queues
Uniform Processing, Variable Values, Shared Memory Switch
Uniform Processing, CIOQ Switches
Uniform Values
Variable Values
Uniform Processing, Crossbar Switches
Uniform Values, Variable Processing, Single Queue
Non-Push-Out Policies
Push-Out Policies
Copying Cost
Uniform Values, Variable Processing, Multiple Separated Queues
Uniform Values, Variable Processing, Shared Memory Switch
Non-Push-Out Policies
Push-Out Policies
Open Problems
Cross-References
Recommended Reading
Single-Source Fully Dynamic Reachability
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Approaches
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Single-Source Shortest Paths
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Experimental Results
Data Sets
URL to Code
Cross-References
Recommended Reading
Ski Rental Problem
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
History and Further Reading
Cross-References
Recommended Reading
Slicing Floorplan Orientation
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Slicing Floorplan
Slicing Tree
Orientation Optimization
Key Results
Pseudocode Stockmeyer()
Correctness
Runtime
Applications
Recommended Reading
Sliding Window Algorithms
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Formal Definition
History
Key Results
Smooth Histogram
Applications
Open Problems
Recommended Reading
Smooth Surface and Volume Meshing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Surface Meshing
Volume Meshing
URLs to Code and Data Sets
Cross-References
Recommended Reading
Smoothed Analysis
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Simplex Method
Binary Optimization Problems
Open Problems
Cross-References
Recommended Reading
Snapshots in Shared Memory
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
A Simple Non-blocking Implementation from Small Registers
Wait-Free Implementations fromLarge Registers
Wait-Free Implementations from Small, Stronger Objects
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Sorting by Transpositions and Reversals (Approximate Ratio 1.5)
Keywords
Problem Definition
Notations and Definition
Key Results
Linear vs. Circular Permutations
The Breakpoint Graph
Transformation into 3-Permutations
Cycle Types
Cycle Configurations
The Algorithm
Applications
Cross-References
Recommended Reading
Sorting Signed Permutations by Reversal (Reversal Distance)
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Experimental Results
URL to Code
Cross-References
Recommended Reading
Sorting Signed Permutations by Reversal (Reversal Sequence)
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
The O(n4) Self-Reduction
The Quadratic Roof
A Promising New but Still Quadratic Method
Composing with Data Structures
Extensions
Applications
Open Problems
Experimental Results
URL to Code
Cross-References
Recommended Reading
Spanning Trees with Low Average Stretch
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Petal Decomposition
Highways
Cones and Petals
Fast Petal Construction
Ideas in the Analysis
Recommended Reading
Sparse Fourier Transform
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Formal Definition
Related Work
Key Results
Algorithm Overview
One-Sparse Recovery
Partial k-Sparse Recovery
Full k-Sparse Recovery
Recommended Reading
Sparse Graph Spanners
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Sparsest Cut
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Recommended Reading
Speed Scaling
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Recommended Reading
Sphere Packing Problem
Keywords
Years and Authors of Summarized Original Work
Problem Definition
The Congruent Sphere Packing Problem
Key Results
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Split Decomposition via Graph-Labelled Trees
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Graph Classes
Distance Hereditary Graphs
Subclasses of Totally Decomposable Graphs
Circle Graphs
Perfect Graphs
Related Graph Decompositions
Modular Decomposition
Width Parameters
Recommended Reading
Squares and Repetitions
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Stable Marriage
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Stable Marriage and Discrete Convex Analysis
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Discrete Convex Analysis: M#-Concave Functions
Applications
Open Problems
Cross-References
Recommended Reading
Stable Marriage with One-Sided Ties
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Problem 1 (MAX SMOTI)
Problem 2 (MAX SSMTI)
Examples
Key Results
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Stable Marriage with Ties and Incomplete Lists
Synonyms
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notations
Definition of the Approximation Ratio
Key Results
SMTI and MAX SMTI in Super-Stability and Strong Stability
SMTI and MAX SMTI in Weak Stability
(p, q)-MAX SMTI in Weak Stability
Applications
Open Problems
Cross-References
Recommended Reading
Stable Partition Problem
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Trivial Encoding
Anonymous Preferences
Additive Preferences
Preferences Derived from the Best and/or Worst Player
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Stackelberg Games: The Price of Optimum
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Models and Notations
Nonatomic Flows
Atomic Splittable Flows
Atomic Unsplittable Flows
Key Results
Example
Applications
Open Problems
Cross-References
Recommended Reading
Staged Assembly
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Lines
Squares
General Shapes
Applications
Open Problems
Cross-References
Recommended Reading
Statistical Multiple Alignment
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notations
Substitutions
Insertions and Deletions
Evolutionary Trees
Multiple Hidden Markov Models
Key Results
Applications
Open Problems
Recommended Reading
Statistical Query Learning
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Definitions and Notation
Key Results
Statistical Queries and Noise-Tolerance
Statistical Query Algorithms
Statistical Query Dimension
Applications
Open Problems
Cross-References
Recommended Reading
Statistical Timing Analysis
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Orthogonalizing Process Parameter Distributions
Gate Delay Distribution
Circuit Delay Distribution
Applications
Experimental Results
URLs to Code and Data Sets
Recommended Reading
Steiner Forest
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Formal Definition and Notation
Related Problems
Key Results
Related Work
Primal-Dual Algorithm
Applications
Cross-References
Recommended Reading
Steiner Trees
Keywords
Years and Authors of Summarized Original Work
Definition
History and Background
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Stochastic Knapsack
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Extensions
Correlated Stochastic Knapsack
Budgeted Multi-armed Bandit
Stochastic Orienteering
Applications
Open Problems
Recommended Reading
Stochastic Scheduling
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Cross-References
Recommended Reading
String Matching
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Online Text Parsing
Algorithms Sublinear on the Average
Time-Space Optimal Algorithms
Bit-Parallel Solution
Applications
Open Problems
Experimental Results
URLs to Code and Data Sets
Cross-References
Recommended Reading
String Sorting
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Experimental Results
Data Sets
URL to Code
Cross-References
Recommended Reading
Strongly Connected Dominating Set
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Hardness Results
MSCDAS in General Digraph
MSCDAS in Disk Graph
Applications
Open Problems
Recommended Reading
Subexponential Parameterized Algorithms
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
FAST
Fill-In
Completion to Graph Classes
Open Problems
Cross-References
Recommended Reading
Subset Sum Algorithm for Bin Packing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Lower Bound on R∞SS
Upper Bound on R∞SS
Parametric Case
Applications
Experimental Results
Cross-References
Recommended Reading
Substring Parsimony
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
URL to Code
Cross-References
Recommended Reading
Succinct and Compressed Data Structures for Permutations and Integer Functions
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Succinct Data Structures
``Shortcut'' Index Supporting π() and π-1()
``Cycle'' Data Structure Supporting πk()
``Benes Network'' Data Structure Supporting πk()
Compressed Data Structures
Runs
Heads of Strict Runs
Shuffled Subsequences
LRM Subsequences
Number of Inversions
Removing Elements
Applications
Integer Functions
Open Problems
Other Measures of Disorder
Sorting and Encoding Multisets
Compressed Data Structures Supporting πk()
Recommended Reading
Succinct Data Structures for Parentheses Matching
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Balanced Parentheses
Trees
Graphs
Key Results
Applications
Succinct Representation of Suffix Trees
Succinct Representation of Functions
Multiple Parentheses and Graphs
Open Problems
Experimental Results
Cross-References
Recommended Reading
Suffix Array Construction
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Experimental Results
URLs to Code and Data Sets
Cross-References
Recommended Reading
Suffix Tree Construction
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notations
Constraints
Key Results
Applications
Open Problems
Experimental Results
URLs to Code and Data Sets
Cross-References
Recommended Reading
Suffix Tree Construction in Hierarchical Memory
Keywords
Years and Authors of Summarized Original Work
Problem Definition
The Model of Computation
Notation
Key Results
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Suffix Trees and Arrays
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Top-Down
Bottom-Up
Top-Down and Suffix Links
Top-Down in the Suffix-Link Tree
Any Order
String Depth Annotation
Frequency Annotation
String Depth and Frequency Annotation
Positional Annotations
Applications
Cross-References
Recommended Reading
Sugiyama Algorithm
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Reduction of the Number of Edge Crossings
Determination of x-Coordinates of Vertices
Applications
Cross-References
Recommended Reading
Superiority and Complexity of the Spaced Seeds
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Support Vector Machines
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Classification
Maximizing the Margin
Key Results
Soft Margin
Regression
Speeding Up the Quadratic Program
Kernel Methods
Choosing the Kernel
Kernels for General Data
Applications
Text Categorization
Handwritten Character Recognition
Bioinformatics
URL to Code
Cross-References
Recommended Reading
Surface Reconstruction
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Crust Algorithm
Cocone Algorithm
Powercrust Algorithm
Noisy Samples
Complexity
Applications
Open Problems
URLs to Code and Data Sets
Cross-References
Recommended Reading
Symbolic Model Checking
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Hardware Verification
State Explosion
Hardware Model
Invariant Checking
Key Results
Image Computation
Invariant Checking
Applications
Experimental Results
Data Sets
Cross-References
Recommended Reading
Symmetric Graph Drawing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Computing a Planar Automorphism Group of Maximum Size
Overview of the Drawing Algorithm
The Cyclic Case
One Axial Symmetry
The Dihedral Case
Cross-References
Recommended Reading
Synchronizers, Spanners
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
T
Table Compression
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notations
Combinatorial Dependency and Joint Entropy of Random Variables
Column Dependency and Conditional Entropy of Random Variables
Key Results
Combinatorial Dependency
Column Dependency
Motifs
Applications
Open Problems
Experimental Results
Data Sets
URL to Code
Cross-References
Recommended Reading
Tail Bounds for Occupancy Problems
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Cross-References
Recommended Reading
Technology Mapping
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Recommended Reading
Teleportation of Quantum States
Keywords
Synonyms
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Super-Dense Coding
Lower Bounds on Resources
Remote State Preparation
Teleportation as a Private Quantum Channel
Quantum State Redistribution
Applications
Experimental Results
Cross-References
Recommended Reading
Temperature Programming in Self-Assembly
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Thin Rectangles
Squares
Scaled Finite Shapes
Open Problems
Cross-References
Recommended Reading
Testing Bipartiteness in the Dense-Graph Model
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Comments for the Recommended Reading
Recommended Reading
Testing Bipartiteness of Graphs in Sublinear Time
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Cross-References
Comments for the Recommended Reading
Recommended Reading
Testing if an Array Is Sorted
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Bibliographical Notes
Key Results
Hamming Testers for Sortedness
A Tester Based on Binary Search ch700:EKKRV00
Analysis of the First Tester
A Tester Based on Graph Spanners ch700:BGJRW12
Analysis of the Second Tester
L1-Tester for Sortedness
Running time
Applications
Open Problem
Cross-References
Recommended Reading
Testing Juntas and Related Properties of Boolean Functions
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Testing 1-Juntas
Testing k-Juntas
Junta-Testing Algorithm
Applications
Feature Selection
Testing by Implicit Learning
Testing Function Isomorphism
Open Problems
Distance Approximation
Testing with Random Samples
Cross-References
Recommended Reading
Text Indexing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Three-Dimensional Graph Drawing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Track Layouts
An Algorithm for Graphs of Bounded Treewidth
Other Models for 3D Graph Drawing
Recommended Reading
Thresholds of Random k-Sat
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Algorithm Greedy
Algorithm CL
Applications
Open Problems
Cross-References
Recommended Reading
Topology Approach in Distributed Computing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Trade-Offs for Dynamic Graph Problems
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Dynamic Transitive Closure
Dynamic Shortest Paths
Applications
Open Problems
Cross-References
Recommended Reading
Transactional Memory
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
TM C/C++ Specification and Compiler Support
HTM in Mainstream Processors
STM Implementations
Hardware Lock Elision
Hybrid TM
TM Applications
Cross-References
Recommended Reading
Traveling Sales Person with Few Inner Points
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results*-1pc
Applications
Open Problems
Cross-References
Recommended Reading
Tree Enumeration
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Enumeration of All Ordered Trees
Enumeration of All Unordered Trees
Cross-References
Recommended Reading
Treewidth of Graphs
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Experimental Results
Data Sets
Cross-References
Recommended Reading
Trial and Error Algorithms
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Time Complexity
Trial Complexity
Key Results
Related Work
Learning
Ellipsoid Method
Cross-References
Recommended Reading
Triangulation Data Structures
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Mesh Structures: Definition
Data Structures: Classification
Standard Mesh Representations
Key Results
A Theoretically Optimal Representation
A More Practical Solution
Reducing Redundancy Throughout Face Reordering
More Compact (Static) Representations
A Dynamic Representation
Experimental Results
Cross-References
Recommended Reading
Truthful Mechanisms for One-Parameter Agents
Keywords
Synonyms
Years and Authors of Summarized Original Work
Problem Definition
The Mechanism Design Framework
Scheduling on Related Machines
Key Results
Applications
Open Problems
Experimental Results
Data Sets
URL to Code
Cross-References
Recommended Reading
Truthful Multicast
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notations
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
TSP-Based Curve Reconstruction
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Finite Precision
Relation to Local Feature Size
Applications
Open Problems
Experimental Results
Data Sets
URL to Code
Cross-References
Recommended Reading
Two-Dimensional Scaled Pattern Matching
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Two-Interval Pattern Problems
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notations
Constraints
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
U
Undirected Feedback Vertex Set
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Recommended Reading
Unified View of Graph Searching and LDFS-Based Certifying Algorithms
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Problem Definition (cont.)
Key Results (cont.)
Open Problems
Recommended Reading
Uniform Covering of Rings and Lines by Memoryless Mobile Sensors
Keywords
Years and Authors of Summarized Original Work
Problem Definition
The Model
The Problem
Key Results
The Ring
Exact Uniform Covering
Approximate Covering
The Line
Exact Uniform Covering
Approximate Covering
Applications
Open Problems
Recommended Reading
Unique k-SAT and General k-SAT
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Open Problems
Cross-References
Recommended Reading
Universal Sequencing on an Unreliable Machine
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Bounding the Performance of a Universal Sequence
A Universal Sequencing Algorithm
Randomized Universal Schedules
Generalizations
Global Cost Functions
Precedence Constraints
Release Dates
Instance-Sensitive Performance Guarantee
Applications
Open Problems
Cross-References
Recommended Reading
Upward Graph Drawing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Polynomial-Time Upward Planarity Testing
Applications
Experimental Results
Cross-References
Recommended Reading
Utilitarian Mechanism Design for Single-Minded Agents
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Utilitarian Mechanism Design
Mechanism
Monotonicity
Additional Definitions
Key Results
Monotone Approximation Schemes
Truthful Primal-Dual Mechanisms
Applications
Applications of Monotone Approximation Schemes
Applications of the primal dual algorithms
Survey of Other Results
Cross-References
Recommended Reading
V
Vector Bin Packing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Generalizations of Classical Bin Packing Algorithms
Generalizing First Fit and First Fit Decreasing
Generalizing the de la Vega and Lueker Asymptotic Approximation Scheme
Hardness of Approximation Results
Algorithms with RA∞(d) < d
Experimental Results
Cross-References
Recommended Reading
Vector Scheduling Problems
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Constant Dimension d
General Dimension d
Extensions
Open Problems
Cross-References
Recommended Reading
Vertex Cover Kernelization
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Preprocessing Based on Vertex Degrees
Nemhauser-Trotter Theorem
A Faster Nemhauser-Trotter Construction
Crown Reduction
Applications
Experimental Results
Data Sets
Cross-References
Recommended Reading
Vertex Cover Search Trees
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Kernelization
Folding
Branch and Search
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Visualization Techniques for Algorithm Engineering
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Critical Issues
Techniques
Event-Driven Visualization
State Mapping Visualization
Applications
Open Problems
Cross-References
Recommended Reading
Voltage Scheduling
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notations and Definitions
Assumptions
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Voronoi Diagrams and Delaunay Triangulations
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Generalizations
Key Results
Divide and Conquer
Sweep
Reduction to Convex Hull
Incremental Construction
Applications
Cross-References
Recommended Reading
W
Wait-Free Synchronization
Years and Authors of Summarized Original Work
Problem Definition
Weaker Nonblocking Progress Conditions
Transactional Memory
Key Results
Applications
Open Questions
Cross-References
Recommended Reading
Wake-Up Problem in Multi-Hop Radio Networks
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Synchronizers
Key Results
A Deterministic Wake-Up Protocol
A Randomized Wake-Up Protocol
Applications
Universal Synchronizers and Faster Wake-Up Protocols
Leader Election and Clock Synchronization
Open Problems
Cross-References
Recommended Reading
Wavelet Trees
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Compressed Sequences
Geometric Points and Two-Dimensional Data
Permutations, Shufflings, and Reorderings
Applications
Cross-References
Recommended Reading
Weighted Connected Dominating Set
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notations
Key Results
Applications
Open Problems
Experimental Results
Cross-References
Recommended Reading
Weighted Popular Matchings
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Cross-References
Recommended Reading
Weighted Random Sampling
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Definitions
Notation and Assumptions
Key Results
Applications
URL to Code
Cross-References
Recommended Reading
Well Separated Pair Decomposition
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Unit-Disk Graphs
Metric Space
Well-Separated Pair Decomposition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Well Separated Pair Decomposition for Unit-Disk Graph
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Notations
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Wire Sizing
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
Work-Function Algorithm for k-Servers
Keywords
Years and Authors of Summarized Original Work
Problem Definition
Key Results
Applications
Open Problems
Cross-References
Recommended Reading
List of Entries
Ming-Yang Kao
Editor-in-Chief
Encyclopedia of
Algorithms
Second Edition
1 3 Reference
Encyclopedia of Algorithms
Ming-Yang Kao
Editor
Encyclopedia of
Algorithms
Second Edition
With 379 Figures and 51 Tables
Editor
Ming-Yang Kao
Department of Electrical Engineering
and Computer Science
Northwestern University
Evanston, IL, USA
ISBN 978-1-4939-2863-7
ISBN 978-1-4939-2865-1
DOI 10.1007/ 978-1-4939-2864-4
(print and electronic bundle)
ISBN 978-1-4939-2864-4
(eBook)
Library of Congress Control Number: 2015958521
© Springer Science+Business Media New York 2008, 2016
This work is subject to copyright. All rights are reserved by the Publisher, whether the whole
or part of the material is concerned, specifically the rights of translation, reprinting, reuse of
illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way,
and transmission or information storage and retrieval, electronic adaptation, computer software,
or by similar or dissimilar methodology now known or hereafter developed.
The use of general descriptive names, registered names, trademarks, service marks, etc. in this
publication does not imply, even in the absence of a specific statement, that such names are
exempt from the relevant protective laws and regulations and therefore free for general use.
The publisher, the authors and the editors are safe to assume that the advice and information in
this book are believed to be true and accurate at the date of publication. Neither the publisher
nor the authors or the editors give a warranty, express or implied, with respect to the material
contained herein or for any errors or omissions that may have been made.
Printed on acid-free paper
This Springer imprint is published by SpringerNature
The registered company is Springer Science+Business Media LLC New York
Preface
The Encyclopedia of Algorithms provides researchers, students, and
practitioners of algorithmic research with a mechanism to efficiently
and accurately find the names, definitions, and key results of important
algorithmic problems. It also provides further readings on those problems.
This encyclopedia covers a broad range of algorithmic areas; each area
is summarized by a collection of entries. The entries are written in a clear
and concise structure so that they can be readily absorbed by the readers and
easily updated by the authors. A typical encyclopedia entry is an in-depth
mini-survey of an algorithmic problem written by an expert in the field. The
entries for an algorithmic area are compiled by area editors to survey the
representative results in that area and can form the core materials of a course
in the area.
This 2nd edition of the encyclopedia contains a wide array of impor-
tant new research results. Highlights include works in tile self-assembly
(nanotechnology), bioinformatics, game theory, Internet algorithms, and
social networks. Overall, more than 70 % of the entries in this edition and
new entries are updated.
This reference work will continue to be updated on a regular basis via a
live site to allow timely updates and fast search. Knowledge accumulation
is an ongoing community project. Please take ownership of this body of
work. If you have feedback regarding a particular entry, please feel free to
communicate directly with the author or the area editor of that entry. If you
are interested in authoring a future entry, please contact a suitable area editor.
If you have suggestions on how to improve the Encyclopedia as a whole,
please contact me at kao@northwestern.edu. The credit of this Encyclopedia
goes to the area editors, the entry authors, the entry reviewers, and the project
editors at Springer, including Melissa Fearon, Michael Hermann, and Sylvia
Blago.
v
About the Editor
and Computer
Ming-Yang Kao is a Professor of Computer
in the Department of Electrical
Science
Engineering
at
Northwestern University. He has published
extensively in the design,
and
applications of algorithms. His current interests
include discrete optimization, bioinformatics,
computational
computational
finance, and nanotechnology. He serves as the
Editor-in-Chief of Algorithmica.
economics,
Science
analysis,
He obtained a B.S. in Mathematics from
National Taiwan University in 1978 and a Ph.D.
in Computer Science from Yale University in 1986. He previously taught
at Indiana University at Bloomington, Duke University, Yale University,
and Tufts University. At Northwestern University, he has served as the
Department Chair of Computer Science. He has also cofounded the Program
in Computational Biology and Bioinformatics and served as its Director. He
currently serves as the Head of the EECS Division of Computing, Algorithms,
and Applications and is a Member of the Theoretical Computer Science
Group.
For more information, please see www.cs.northwestern.edu/~kao
vii
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
