Algorithms and Computation: 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part I (Lecture Notes in Computer Science, 6506)

This volume contains the proceedings of the 21st Annual International S- posium on Algorithms and Computations (ISAAC 2010), held in Jeju, Korea during December 15-17, 2010. Past editions have been held in Tokyo, Taipei, Nagoya,HongKong,Beijing,Cairns,Osaka,Singapore,Taejon,Chennai,Taipei, Christchurch, Vancouver, Kyoto, Hong Kong, Hainan, Kolkata, Sendai, Gold Coast, and Hawaii over the years 1990-2009. ISAACis anannualinternationalsymposiumthatcoversthe verywide range of topics in algorithms and computation. The main purpose of the symposium is to provide a forum for researchers working in algorithms and the theory of computation where they can exchange ideas in this active research community. In response to the call for papers, ISAAC 2010 received 182 papers. Each submission was reviewed by at least three Program Committee members with the assistance of external referees. Since there were many high-quality papers, the Program Committee's task was extremely di?cult. Through an extensive discussion, the Program Committee accepted 77 of the submissions to be p- sented at the conference. Two special issues, one of Algorithmica and one of the International Journal of Computational Geometry and Applications,were prepared with selected papers from ISAAC 2010. The best paper award was given to "From Holant to #CSP and Back: c DichotomyforHolant Problems"byJin-YiCai,SangxiaHuangandPinyanLu, and the best student paper award to "Satis?ability with Index Dependency" by Hongyu Liang and Jing He. Two eminent invited speakers,David Eppstein from UniversityofCalifornia,Irvine,andMattFranklinfromUniversityofCalifornia, Davis, also contributed to this volume 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 - Annotation. This book constitutes the refereed proceedings of the 21st International Symposium on Algorithms and Computation, ISAAC 2010, held in Jeju, South Korea in December 2010. The 77 revised full papers presented were carefully reviewed and selected from 182 submissions for inclusion in the book. This volume contains topics such as approximation algorithm; complexity; data structure and algorithm; combinatorial optimization; graph algorithm; computational geometry; graph coloring; fixed parameter tractability; optimization; online algorithm; and scheduling Constitutes the refereed proceedings of the 21st International Symposium on Algorithms and Computation, ISAAC 2010, held in Jeju, South Korea in December 2010. This volume contains topics such as approximation algorithm; complexity; data structure and algorithm; combinatorial optimization; graph algorithm; and, computational geometry.