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.
Author(s): David Eppstein (auth.), Otfried Cheong, Kyung-Yong Chwa, Kunsoo Park (eds.)
Series: Lecture Notes in Computer Science 6506 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2010
Language: English
Pages: 465
Tags: Algorithm Analysis and Problem Complexity; Discrete Mathematics in Computer Science; Computer Communication Networks; Computer Graphics; Data Structures; Numeric Computing
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 -
