Algorithms and Computation: 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part I

Front Matter....Pages -
Regular Labelings and Geometric Structures....Pages 1-1
Algorithmic Aspects of Secure Computation and Communication....Pages 2-2
Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament....Pages 3-14
A 3/2-Approximation Algorithm for Generalized Steiner Trees in Complete Graphs with Edge Lengths 1 and 2....Pages 15-24
Approximate Periodicity....Pages 25-36
Approximating the Average Stretch Factor of Geometric Graphs....Pages 37-48
Satisfiability with Index Dependency....Pages 49-60
Anonymous Fuzzy Identity-Based Encryption for Similarity Search....Pages 61-72
Improved Randomized Algorithms for 3-SAT....Pages 73-84
Quantum Counterfeit Coin Problems....Pages 85-96
Priority Range Trees....Pages 97-108
Should Static Search Trees Ever Be Unbalanced?....Pages 109-120
Levelwise Mesh Sparsification for Shortest Path Queries....Pages 121-132
Unit-Time Predecessor Queries on Massive Data Sets....Pages 133-144
Popularity at Minimum Cost....Pages 145-156
Structural and Complexity Aspects of Line Systems of Graphs....Pages 157-168
Neighbor Systems, Jump Systems, and Bisubmodular Polyhedra....Pages 169-181
Generating Trees on Multisets....Pages 182-193
Seidel Minor, Permutation Graphs and Combinatorial Properties....Pages 194-205
Simultaneous Interval Graphs....Pages 206-217
Unbalanced Graph Partitioning....Pages 218-229
On the Intersection of Tolerance and Cocomparability Graphs....Pages 230-240
Flows in One-Crossing-Minor-Free Graphs....Pages 241-252
From Holant to #CSP and Back: Dichotomy for Holant c Problems....Pages 253-265
Computing Sparse Multiples of Polynomials....Pages 266-278
Fractal Parallelism: Solving SAT in Bounded Space and Time....Pages 279-290
Interpretation of Stream Programs: Characterizing Type 2 Polynomial Time Complexity....Pages 291-303
New Upper Bounds on the Average PTF Density of Boolean Functions....Pages 304-315
An Optimal Algorithm for Computing Angle-Constrained Spanners....Pages 316-327
Approximating Minimum Bending Energy Path in a Simple Corridor....Pages 328-339
Analysis of an Iterated Local Search Algorithm for Vertex Coloring....Pages 340-352
Bounded Max-colorings of Graphs....Pages 353-365
Parameterized Algorithms for Boxicity....Pages 366-377
On Tractable Cases of Target Set Selection....Pages 378-389
Combining Two Worlds: Parameterised Approximation for Vertex Cover....Pages 390-402
Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time....Pages 403-414
Lower Bounds for Howard’s Algorithm for Finding Minimum Mean-Cost Cycles....Pages 415-426
Solving Two-Stage Stochastic Steiner Tree Problems by Two-Stage Branch-and-Cut....Pages 427-439
An Optimal Algorithm for Single Maximum Coverage Location on Trees and Related Problems....Pages 440-450
A Faster Algorithm for the Maximum Even Factor Problem....Pages 451-462
Back Matter....Pages -