Algorithms and Computation: 22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5-8, 2011. Proceedings (Lecture Notes in Computer Science, 7074)

Annotation This book constitutes the refereed proceedings of the 22nd International Symposium on Algorithms and Computation, ISAAC 2011, held in Yokohama, Japan in December 2011. The 76 revised full papers presented together with two invited talks were carefully reviewed and selected from 187 submissions for inclusion in the book. This volume contains topics such as approximation algorithms; computational geometry; computational biology; computational complexity; data structures; distributed systems; graph algorithms; graph drawing and information visualization; optimization; online and streaming algorithms; parallel and external memory algorithms; parameterized algorithms; game theory and internet algorithms; randomized algorithms; and string algorithms 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 -