Algorithms and Computation

ISAAC 2005, the 16th International Symposium on Algorithms and Computation, took place in Hainan, China, December 19-21, 2005. The symposium provided a forum for researchers working in algorithms and the theory of computation from all over the world. The final count of electronic submissions was 549, of which 112 were accepted. Among them, the submitting authors emails are: 18 from edu (USA) - counts, 14 from de (Germany), 10 from jp (Japan), 8 from fr (France), 8 from hk (Hong Kong), 7 from ca (Canada), 6 from cn (China), 5 from gr (Greece), 4 from gmail, 3 from tw (Taiwan), 3 from it (Italy), 3 from se (Sweden), 3 from sg (Sin- pore), 2 from cz (Czech Republic), 2 from ch (Switzerland), 2 from 163. com, and 1 each from no (Norway), uk (United Kingdom), be (Belgium), au (Australia), es (Spain), nl (The Netherlands), kr (Korea), in (India), il (Israel), cy (Cyprus), cl (Chile), pl (Poland), ie (Ireland), and net. This represents a total of 30 countries or regions, including 3 Internet dot coms. We would like to thank the two invited speaker, Mihalis Yannakakis and Frances Y. Yao, for their insightful speeches and new directions in algorithms and computation. We received 6 nominations for the best paper and 6 nominations for the best s- dent paper. Only papers with all co-authors students could qualify for the latter.

Algorithmic Problems in Wireless Ad Hoc Networks.- Algorithmic Problems in Wireless Ad Hoc Networks.- Probability and Recursion.- Embedding Point Sets into Plane Graphs of Small Dilation.- The Layered Net Surface Problems in Discrete Geometry and Medical Image Segmentation.- Separability with Outliers.- Casting an Object with a Core.- Sparse Geometric Graphs with Small Dilation.- Multiple Polyline to Polygon Matching.- Minimizing a Monotone Concave Function with Laminar Covering Constraints.- Almost Optimal Solutions for Bin Coloring Problems.- GEN-LARAC: A Generalized Approach to the Constrained Shortest Path Problem Under Multiple Additive Constraints.- Simultaneous Matchings.- An Optimization Problem Related to VoD Broadcasting.- A Min-Max Relation on Packing Feedback Vertex Sets.- Average Case Analysis for Tree Labelling Schemes.- Revisiting T. Uno and M. Yagiura s Algorithm.- Generating Cut Conjunctions and Bridge Avoiding Extensions in Graphs.- Orthogonal Drawings of Series-Parallel Graphs with Minimum Bends.- Bisecting a Four-Connected Graph with Three Resource Sets.- Laminar Structure of Ptolemaic Graphs and Its Applications.- On the Complexity of the G-Reconstruction Problem.- Hybrid Voting Protocols and Hardness of Manipulation.- On the Complexity of Rocchio s Similarity-Based Relevance Feedback Algorithm.- Correlation Clustering and Consensus Clustering.- An Approximation Algorithm for Scheduling Malleable Tasks Under General Precedence Constraints.- A 1.5-Approximation of the Minimal Manhattan Network Problem.- Hardness and Approximation of Octilinear Steiner Trees.- Dense Subgraph Problems with Output-Density Conditions.- A Complete Characterization of Tolerable Adversary Structures for Secure Point-to-Point Transmissions Without Feedback.- Network Game with Attacker and Protector Entities.- SkipTree: A Scalable Range-Queryable Distributed Data Structure for Multidimensional Data.- The Phase Matrix.- ISB-Tree: A New Indexing Scheme with Efficient Expected Behaviour.- External Data Structures for Shortest Path Queries on Planar Digraphs.- Improved Approximate String Matching Using Compressed Suffix Data Structures.- Monitoring Continuous Band-Join Queries over Dynamic Data.- Approximate Colored Range Queries.- Complexity and Approximation of the Minimum Recombination Haplotype Configuration Problem.- Space Efficient Algorithms for Ordered Tree Comparison.- A 1.75-Approximation Algorithm for Unsigned Translocation Distance.- Fast Algorithms for Computing the Tripartition-Based Distance Between Phylogenetic Networks.- Improved Algorithms for Largest Cardinality 2-Interval Pattern Problem.- Preemptive Semi-online Scheduling on Parallel Machines with Inexact Partial Information.- On-Line Computation and Maximum-Weighted Hereditary Subgraph Problems.- A Novel Adaptive Learning Algorithm for Stock Market Prediction.- Uniformization of Discrete Data.- A Practical Algorithm for the Computation of Market Equilibrium with Logarithmic Utility Functions.- Boosting Spectral Partitioning by Sampling and Iteration.- Smoothed Analysis of Binary Search Trees.- Simple and Efficient Greedy Algorithms for Hamilton Cycles in Random Intersection Graphs.- Counting Distinct Items over Update Streams.- Randomized Algorithm for the Sum Selection Problem.- An Improved Interval Routing Scheme for Almost All Networks Based on Dominating Cliques.- Basic Computations in Wireless Networks.- A Simple Optimal Randomized Algorithm for Sorting on the PDM.- Efficient Parallel Algorithms for Constructing a k-Tree Center and a k-Tree Core of a Tree Network.- A Tight Bound on the Number of Mobile Servers to Guarantee the Mutual Transferability Among Dominating Configurations.- Bounding the Number of Minimal Dominating Sets: A Measure and Conquer Approach.- Collective Tree Spanners in Graphs with Bounded Genus, Chordality, Tree-Width, or Clique-Width.- Sampling Unlabeled Biconnected Planar Graphs.- Configurations with Few Crossings in Topological Graphs.- On Bounded Load Routings for Modeling k-Regular Connection Topologies.- On the Complexity of Global Constraint Satisfaction.- Polynomial Space Suffices for Deciding Nash Equilibria Properties for Extensive Games with Large Trees,.- An Improved -Time Deterministic Algorithm for SAT.- Solving Minimum Weight Exact Satisfiability in Time O(20.2441n ).- Efficient Algorithms for Finding a Longest Common Increasing Subsequence.- Decision Making Based on Approximate and Smoothed Pareto Curves.- Computing Optimal Solutions for the min 3-set covering Problem.- Efficient Algorithms for the Weighted 2-Center Problem in a Cactus Graph.- Algorithms for Local Forest Similarity.- Fast Algorithms for Finding Disjoint Subsequences with Extremal Densities.- A Polynomial Space and Polynomial Delay Algorithm for Enumeration of Maximal Motifs in a Sequence.- 5-th Phylogenetic Root Construction for Strictly Chordal Graphs.- Recursion Theoretic Operators for Function Complexity Classes.- From Balls and Bins to Points and Vertices.- Simulating Undirected st-Connectivity Algorithms on Uniform JAGs and NNJAGs.- Upper Bounds on the Computational Power of an Optical Model of Computation.- Complexity of the Min-Max (Regret) Versions of Cut Problems.- Improved Algorithms for the k Maximum-Sums Problems.- Network Load Games.- Minimum Entropy Coloring.- Algorithms for Max Hamming Exact Satisfiability.- Counting Stable Strategies in Random Evolutionary Games.- Exact and Approximation Algorithms for Computing the Dilation Spectrum of Paths, Trees, and Cycles.- On the Computation of Colored Domino Tilings of Simple and Non-simple Orthogonal Polygons.- Optimal Paths for Mutually Visible Agents.- Stacking and Bundling Two Convex Polygons.- Algorithms for Range-Aggregate Query Problems Involving Geometric Aggregation Operations.- A ( ) Approximation Algorithm for the Stable Marriage Problem.- Approximating the Traffic Grooming Problem.- Scheduling to Minimize Makespan with Time-Dependent Processing Times.- On Complexity and Approximability of the Labeled Maximum/Perfect Matching Problems.- Finding a Weight-Constrained Maximum-Density Subtree in a Tree.- Finding Two Disjoint Paths in a Network with Normalized ? ?+?-MIN-SUM Objective Function.- Sensitivity Analysis of Minimum Spanning Trees in Sub-inverse-Ackermann Time.- Approximation Algorithms for Layered Multicast Scheduling.- Minimum Weight Triangulation by Cutting Out Triangles.- Multi-directional Width-Bounded Geometric Separator and Protein Folding.- Shortest Paths and Voronoi Diagrams with Transportation Networks Under General Distances.- Approximation Algorithms for Computing the Earth Mover s Distance Under Transformations.- Fast k-Means Algorithms with Constant Approximation.- On Efficient Weighted Rectangle Packing with Large Resources.- On Routing in VLSI Design and Communication Networks.- The Capacitated Traveling Salesman Problem with Pickups and Deliveries on a Tree.- Distance Labeling in Hyperbolic Graphs.- Multi-source Trees: Algorithms for Minimizing Eccentricity Cost Metrics.- Edge-Pancyclicity of Twisted Cubes.- Combinatorial Network Abstraction by Trees and Distances.- Drawing Phylogenetic Trees.- Localized and Compact Data-Structure for Comparability Graphs.- Representation of Graphs by OBDDs.- Space-Efficient Construction of LZ-Index.- Longest Increasing Subsequences in Windows Based on Canonical Antichain Partition.- Errata from ISAAC 2004 (LNCS 3341).- Pareto Optimality in House Allocation Problems.- Generalized Geometric Approaches for Leaf Sequencing Problems in Radiation Therapy,.