-
1
-
Algorithmic Challenges in Web Search Engines
-
8
-
RNA Molecules: Glimpses Through an Algorithmic Lens
-
11
-
Squares
-
13
-
Matching Based Augmentations for Approximating Connectivity Problems
-
25
-
Modelling Errors and Recovery for Communication
-
26
-
Lossless Data Compression Via Error Correction
-
28
-
The Power and Weakness of Randomness in Computation
-
30
-
A New GCD Algorithm for Quadratic Number Rings with Unique Factorization
-
43
-
On Clusters in Markov Chains
-
56
-
An Architecture for Provably Secure Computation
-
68
-
Scoring Matrices That Induce Metrics on Sequences
-
80
-
Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams
-
93
-
The Complexity of Diffuse Reflections in a Simple Polygon
-
105
-
Counting Proportions of Sets: Expressive Power with Almost Order
-
118
-
Efficient Approximate Dictionary Look-Up for Long Words over Small Alphabets
-
130
-
Relations Among Notions of Security for Identity Based Encryption Schemes
-
142
-
Optimally Adaptive Integration of Univariate Lipschitz Functions
-
154
-
Classical Computability and Fuzzy Turing Machines
-
166
-
An Optimal Algorithm for the Continuous/Discrete Weighted 2-Center Problem in Trees
-
178
-
An Algorithm for a Generalized Maximum Subsequence Problem
-
190
-
Random Bichromatic Matchings
-
202
-
Eliminating Cycles in the Discrete Torus
-
211
-
On Behalf of the Seller and Society: Bicriteria Mechanisms for Unit-Demand Auctions
-
224
-
Pattern Matching Statistics on Correlated Sources
-
238
-
Robust Model-Checking of Linear-Time Properties in Timed Automata
-
250
-
The Computational Complexity of the Parallel Knock-Out Problem
-
262
-
Reconfigurations in Graphs and Grids
-
274
-
<InlineEquation ID="IEq1">
<InlineMediaObject>
<ImageObject Color="BlackWhite" FileRef="978-3-540-32756-1_28_Chapter_TeX2GIF_IEq1.gif" Format="GIF" Rendition="HTML" Type="Linedraw" />
</InlineMediaObject>
<EquationSource Format="TEX">${\mathcal C}$</EquationSource>
</InlineEquation>-Varieties, Actions and Wreath Product
-
286
-
Local Construction of Planar Spanners in Unit Disk Graphs with Irregular Transmission Ranges
-
298
-
An Efficient Approximation Algorithm for Point Pattern Matching Under Noise
-
311
-
Oblivious Medians Via Online Bidding
-
323
-
Efficient Computation of the Relative Entropy of Probabilistic Automata
-
337
-
A Parallel Algorithm for Finding All Successive Minimal Maximum Subsequences
-
349
-
De Dictionariis Dynamicis Pauco Spatio Utentibus
-
362
-
Customized Newspaper Broadcast: Data Broadcast with Dependencies
-
374
-
On Minimum <Emphasis Type="Italic">k</Emphasis>-Modal Partitions of Permutations
-
386
-
Two Birds with One Stone: The Best of Branchwidth and Treewidth with One Algorithm
-
398
-
Maximizing Throughput in Queueing Networks with Limited Flexibility
-
410
-
Network Flow Spanners
-
423
-
Finding All Minimal Infrequent Multi-dimensional Intervals
-
435
-
Cut Problems in Graphs with a Budget Constraint
-
447
-
Lower Bounds for Clear Transmissions in Radio Networks
-
455
-
Asynchronous Behavior of Double-Quiescent Elementary Cellular Automata
-
467
-
Lower Bounds for Geometric Diameter Problems
-
479
-
Connected Treewidth and Connected Graph Searching
-
491
-
A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs
-
502
-
The Committee Decision Problem
-
515
-
Common Deadline Lazy Bureaucrat Scheduling Revisited
-
524
-
Approximate Sorting
-
532
-
Stochastic Covering and Adaptivity
-
544
-
Algorithms for Modular Counting of Roots of Multivariate Polynomials
-
556
-
Hardness Amplification Via Space-Efficient Direct Products
-
569
-
The Online Freeze-Tag Problem
-
580
-
I/O-Efficient Algorithms on Near-Planar Graphs
-
592
-
Minimal Split Completions of Graphs
-
605
-
Design and Analysis of Online Batching Systems
-
617
-
Competitive Analysis of Scheduling Algorithms for Aggregated Links
-
629
-
A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains
-
641
-
On Sampling in Higher-Dimensional Peer-to-Peer Systems
-
653
-
Mobile Agent Rendezvous in a Synchronous Torus
-
665
-
Randomly Colouring Graphs with Girth Five and Large Maximum Degree
-
677
-
Packing Dicycle Covers in Planar Graphs with No <Emphasis Type="Italic">K</Emphasis>
<Subscript>5</Subscript>–<Emphasis Type="Italic">e</Emphasis> Minor
-
689
-
Sharp Estimates for the Main Parameters of the Euclid Algorithm
-
703
-
Position-Restricted Substring Searching
-
715
-
Rectilinear Approximation of a Set of Points in the Plane
-
727
-
The Branch-Width of Circular-Arc Graphs
-
737
-
Minimal Eulerian Circuit in a Labeled Digraph
-
745
-
Speeding up Approximation Algorithms for NP-Hard Spanning Forest Problems by Multi-objective Optimization
-
757
-
<Emphasis Type="SmallCaps">RISOTTO</Emphasis>: Fast Extraction of Motifs with Mismatches
-
769
-
Minimum Cost Source Location Problems with Flow Requirements
-
781
-
Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms
-
793
-
Constructions of Approximately Mutually Unbiased Bases
-
800
-
Improved Exponential-Time Algorithms for Treewidth and Minimum Fill-In