Algorithms and Computation

Invited Talk.- Modeling and Analyzing Massive Terrain Data Sets.- Coloring Triangle-Free Graphs on Surfaces.- Best Paper Award Presentation.- Integer Representation and Counting in the Bit Probe Model.- 1A Graph Algorithms I.- Minimum Degree Orderings.- Greedy Approximation for Source Location Problem with Vertex-Connectivity Requirements in Undirected Graphs.- Dynamic Distance Hereditary Graphs Using Split Decomposition.- Unifying Two Graph Decompositions with Modular Decomposition.- 1B Computational Geometry I.- Escaping Off-Line Searchers and a Discrete Isoperimetric Theorem.- Geometric Spanner of Segments.- Dilation-Optimal Edge Deletion in Polygonal Cycles.- 2A Complexity I.- Unbounded-Error Classical and Quantum Communication Complexity.- A Spectral Method for MAX2SAT in the Planted Solution Model.- On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices.- The 1-Versus-2 Queries Problem Revisited.- 2B Graph Drawing.- Approximating the Crossing Number of Toroidal Graphs.- Width-Optimal Visibility Representations of Plane Graphs.- Computing Upward Topological Book Embeddings of Upward Planar Digraphs.- Algorithms for the Hypergraph and the Minor Crossing Number Problems.- 3A Distributed Algorithms.- On Mixing and Edge Expansion Properties in Randomized Broadcasting.- Linear Reconfiguration of Cube-Style Modular Robots.- Fast Message Dissemination in Random Geometric Ad-Hoc Radio Networks.- Sensor Network Gossiping or How to Break the Broadcast Lower Bound.- On the Complexity of the “Most General” Undirected Firing Squad Synchronization Problem.- 3B Optimization I.- Capacitated Domination Problem.- The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number.- New Bounds for the Nearly Equitable Edge Coloring Problem.- Approximation to the Minimum Cost Edge Installation Problem.- Approximability of Packing Disjoint Cycles.- 4A Data Structure I.- Succinct Representation of Labeled Graphs.- More Efficient Algorithms and Analyses for Unequal Letter Cost Prefix-Free Coding.- Kinetic Maintenance of Mobile k-Centres on Trees.- Checking Value-Sensitive Data Structures in Sublinear Space.- 4B Game Theory.- Manipulation in Games.- Using Nash Implementation to Achieve Better Frugality Ratios.- The Price of Nash Equilibria in Multicast Transmissions Games.- 5A Database Applications.- An Efficient Algorithm for Enumerating Pseudo Cliques.- Fast Adaptive Diagnosis with a Minimum Number of Tests.- Dynamic Structures for Top-k Queries on Uncertain Data.- Separating Populations with Wide Data: A Spectral Analysis.- 5B Online Algorithms.- A Constant-Competitive Algorithm for Online OVSF Code Assignment.- Average-Case Analysis of Online Topological Ordering.- Energy Efficient Deadline Scheduling in Two Processor Systems.- On the Relative Dominance of Paging Algorithms.- 6A I/O Algorithms.- I/O-Efficient Map Overlay and Point Location in Low-Density Subdivisions.- Geometric Streaming Algorithms with a Sorting Primitive.- External Memory Range Reporting on a Grid.- Approximate Range Searching in External Memory.- 6B Networks.- Faster Treasure Hunt and Better Strongly Universal Exploration Sequences.- Hardness and Approximation of Traffic Grooming.- Depth of Field and Cautious-Greedy Routing in Social Networks.- Locating Facilities on a Network to Minimize Their Average Service Radius.- 7A Optimization II.- Faster Combinatorial Algorithms for Determinant and Pfaffian.- A Polynomial-Time-Delay and Polynomial-Space Algorithm for Enumeration Problems in Multi-criteria Optimization.- The Parameterized Complexity of the Unique Coverage Problem.- Bounded Tree-Width and CSP-Related Problems.- 7B Computational Geometry II.- Covering Points by Unit Disks of Fixed Location.- Geodesic Disks and Clustering in a Simple Polygon.- An O(n 2logn) Time Algorithm for Computing Shortest Paths Amidst Growing Discs in the Plane.- Optimal Triangulation with Steiner Points.- 8A Geometric Applications.- New Algorithm for Field Splitting in Radiation Therapy.- In-Place Algorithm for Image Rotation.- Higher Order Voronoi Diagrams of Segments for VLSI Critical Area Extraction.- 8B Data Structures II.- Distributed Relationship Schemes for Trees.- Fast Evaluation of Union-Intersection Expressions.- A Sub-cubic Time Algorithm for the k-Maximum Subarray Problem.- 9A Computational Geometry III.- Compressing Spatio-temporal Trajectories.- Finding Popular Places.- Maintaining Extremal Points and Its Applications to Deciding Optimal Orientations.- 9B Complexity II.- The Monomial Ideal Membership Problem and Polynomial Identity Testing.- On the Fault Testing for Reversible Circuits.- The Space Complexity of k-Tree Isomorphism.- 10A String.- Algorithms for Computing the Length-Constrained Max-Score Segments with Applications to DNA Copy Number Data Analysis.- Space Efficient Indexes for String Matching with Don’t Cares.- 2-Stage Fault Tolerant Interval Group Testing.- Approximate String Matching with Swap and Mismatch.- 10B Graph Algorithms II.- Minimum Fill-In and Treewidth of Split+?ke and Split+?kv Graphs.- Weighted Treewidth Algorithmic Techniques and Results.- Spanning Trees with Many Leaves in Regular Bipartite Graphs.- Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs.