Algorithms and Computation: 22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5-8, 2011. Proceedings

Front Matter....Pages -
Algorithm Engineering for Route Planning – An Update –....Pages 1-5
Semidefinite Programming and Approximation Algorithms: A Survey....Pages 6-9
The School Bus Problem on Trees....Pages 10-19
Improved Approximations for Buy-at-Bulk and Shallow-Light k -Steiner Trees and ( k ,2)-Subgraph....Pages 20-29
Improved Approximation Algorithms for Routing Shop Scheduling....Pages 30-39
Contraction-Based Steiner Tree Approximations in Practice....Pages 40-49
Covering and Piercing Disks with Two Centers....Pages 50-59
Generating Realistic Roofs over a Rectilinear Polygon....Pages 60-69
Computing the Visibility Polygon Using Few Variables....Pages 70-79
Minimizing Interference in Ad-Hoc Networks with Bounded Communication Radius....Pages 80-89
Hamiltonian Paths in the Square of a Tree....Pages 90-99
Dominating Induced Matchings for P 7 -free Graphs in Linear Time....Pages 100-109
Finding Contractions and Induced Minors in Chordal Graphs via Disjoint Paths....Pages 110-119
Recognizing Polar Planar Graphs Using New Results for Monopolarity....Pages 120-129
Robustness of Minimum Cost Arborescences....Pages 130-139
Path Queries in Weighted Trees....Pages 140-149
Dynamic Range Majority Data Structures....Pages 150-159
Dynamic Range Selection in Linear Space....Pages 160-169
A Dynamic Stabbing-Max Data Structure with Sub-Logarithmic Query Time....Pages 170-179
Encoding 2D Range Maximum Queries....Pages 180-189
Diameter and Broadcast Time of Random Geometric Graphs in Arbitrary Dimensions....Pages 190-199
Broadcasting in Heterogeneous Tree Networks with Uncertainty....Pages 200-209
Optimal File Distribution in Peer-to-Peer Networks....Pages 210-219
Animal Testing....Pages 220-229
Cutting Out Polygons with a Circular Saw....Pages 230-239
Fast Fréchet Queries....Pages 240-249
Angle-Restricted Steiner Arborescences for Flow Map Layout....Pages 250-259
Treemaps with Bounded Aspect Ratio....Pages 260-270
Simultaneous Embedding of Embedded Planar Graphs....Pages 271-280
Linear-Time Algorithms for Hole-Free Rectilinear Proportional Contact Graph Representations....Pages 281-291
Fully Retroactive Approximate Range and Nearest Neighbor Searching....Pages 292-301
Compact Representation of Posets....Pages 302-311
Explicit Array-Based Compact Data Structures for Triangulations....Pages 312-322
Space-Efficient Data-Analysis Queries on Grids....Pages 323-332
A Polynomial Kernel for Feedback Arc Set on Bipartite Tournaments....Pages 333-343
Fixed-Parameter Complexity of Feedback Vertex Set in Bipartite Tournaments....Pages 344-353
Parameterized Algorithms for Inclusion of Linear Matchings....Pages 354-363
Computational Study on Bidimensionality Theory Based Algorithm for Longest Path Problem....Pages 364-373
Sorting, Searching, and Simulation in the MapReduce Framework....Pages 374-383
External-Memory Multimaps....Pages 384-394
External Memory Orthogonal Range Reporting with Fast Updates....Pages 395-404
Analysis of Speedups in Parallel Evolutionary Algorithms for Combinatorial Optimization....Pages 405-414
Verifying Nash Equilibria in PageRank Games on Undirected Web Graphs....Pages 415-424
Improved Collaborative Filtering....Pages 425-434
Asymptotic Modularity of Some Graph Classes....Pages 435-444
Program Size and Temperature in Self-Assembly....Pages 445-453
Optimization, Randomized Approximability, and Boolean Constraint Satisfaction Problems....Pages 454-463
Lower Bounds for Myopic DPLL Algorithms with a Cut Heuristic....Pages 464-473
Algorithm for Single Allocation Problem on Hub-and-Spoke Networks in 2-Dimensional Plane....Pages 474-483
Packing-Based Approximation Algorithm for the k -Set Cover Problem....Pages 484-493
Capacitated Domination: Constant Factor Approximations for Planar Graphs....Pages 494-503
On Power-Law Distributed Balls in Bins and Its Applications to View Size Estimation....Pages 504-513
A Randomized Algorithm for Finding Frequent Elements in Streams Using O(loglog N ) Space....Pages 514-523
A Nearly-Quadratic Gap between Adaptive and Non-adaptive Property Testers....Pages 524-533
Online Linear Optimization over Permutations....Pages 534-543
On the Best Possible Competitive Ratio for Multislope Ski Rental....Pages 544-553
Input-Thrifty Extrema Testing....Pages 554-563
Edit Distance to Monotonicity in Sliding Windows....Pages 564-573
Folding Equilateral Plane Graphs....Pages 574-583
Efficient Algorithms for the Weighted k -Center Problem on a Real Line....Pages 584-593
Outlier Respecting Points Approximation....Pages 594-603
An Improved Algorithm for Reconstructing a Simple Polygon from the Visibility Angles....Pages 604-613
The Parameterized Complexity of Local Search for TSP, More Refined....Pages 614-623
On the Parameterized Complexity of Consensus Clustering....Pages 624-633
Two Fixed-Parameter Algorithms for the Cocoloring Problem....Pages 634-642
Parameterized Complexity of the Firefighter Problem....Pages 643-652
Faster Approximate Pattern Matching in Compressed Repetitive Texts....Pages 653-662
A New Algorithm for the Characteristic String Problem under Loose Similarity Criteria....Pages 663-672
Succinct Indexes for Circular Patterns....Pages 673-682
Range LCP....Pages 683-692
Computing Knapsack Solutions with Cardinality Robustness....Pages 693-702
Max-Throughput for (Conservative) k -of- n Testing....Pages 703-713
Closest Periodic Vectors in L p Spaces....Pages 714-723
Maximum Weight Digital Regions Decomposable into Digital Star-Shaped Regions....Pages 724-733
Finding Maximum Sum Segments in Sequences with Uncertainty....Pages 734-743
Algorithms for Building Consensus MUL-trees....Pages 744-753
Adaptive Phenotype Testing for AND/OR Items....Pages 754-763
An Index Structure for Spaced Seed Search....Pages 764-772
Back Matter....Pages -