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

Invited Talks.- Regular Labelings and Geometric Structures.- Algorithmic Aspects of Secure Computation and Communication.- Session 1A. Approximation Algorithm I.- Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament.- A 3/2-Approximation Algorithm for Generalized Steiner Trees in Complete Graphs with Edge Lengths 1 and 2.- Approximate Periodicity.- Approximating the Average Stretch Factor of Geometric Graphs.- Session 1B. Complexity I.- Satisfiability with Index Dependency.- Anonymous Fuzzy Identity-Based Encryption for Similarity Search.- Improved Randomized Algorithms for 3-SAT.- Quantum Counterfeit Coin Problems.- Session 2A. Data Structure and Algorithm I.- Priority Range Trees.- Should Static Search Trees Ever Be Unbalanced?.- Levelwise Mesh Sparsification for Shortest Path Queries.- Unit-Time Predecessor Queries on Massive Data Sets.- Session 2B. Combinatorial Optimization.- Popularity at Minimum Cost.- Structural and Complexity Aspects of Line Systems of Graphs.- Neighbor Systems, Jump Systems, and Bisubmodular Polyhedra.- Generating Trees on Multisets.- Session 3A. Graph Algorithm I.- Seidel Minor, Permutation Graphs and Combinatorial Properties.- Simultaneous Interval Graphs.- Unbalanced Graph Partitioning.- On the Intersection of Tolerance and Cocomparability Graphs.- Flows in One-Crossing-Minor-Free Graphs.- Session 3B. Complexity II.- From Holant to #CSP and Back: Dichotomy for Holant c Problems.- Computing Sparse Multiples of Polynomials.- Fractal Parallelism: Solving SAT in Bounded Space and Time.- Interpretation of Stream Programs: Characterizing Type 2 Polynomial Time Complexity.- New Upper Bounds on the Average PTF Density of Boolean Functions.- Session 4A. Computational Geometry I.- An Optimal Algorithmfor Computing Angle-Constrained Spanners.- Approximating Minimum Bending Energy Path in a Simple Corridor.- Session 4B. Graph Coloring I.- Analysis of an Iterated Local Search Algorithm for Vertex Coloring.- Bounded Max-colorings of Graphs.- Session 5A. Fixed Parameter Tractability.- Parameterized Algorithms for Boxicity.- On Tractable Cases of Target Set Selection.- Combining Two Worlds: Parameterised Approximation for Vertex Cover.- Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time.- Session 5B. Optimization.- Lower Bounds for Howard’s Algorithm for Finding Minimum Mean-Cost Cycles.- Solving Two-Stage Stochastic Steiner Tree Problems by Two-Stage Branch-and-Cut.- An Optimal Algorithm for Single Maximum Coverage Location on Trees and Related Problems.- A Faster Algorithm for the Maximum Even Factor Problem.