Algorithms and Computation: 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17-19, 2007. Proceedings

Pankaj K. Agarwal (auth.), Takeshi Tokuyama (eds.)3540771182, 9783540771180

This book constitutes the refereed proceedings of the 18th International Symposium on Algorithms and Computation, ISAAC 2007, held in Sendai, Japan, in December 2007.

The 77 revised full papers presented together with 2 invited talks were carefully reviewed and selected from 220 submissions. The papers are organized in topical sections on graph algorithms, computational geometry, complexity, graph drawing, distributed algorithms, optimization, data structure, game theory, database applications, online algorithms, I/O algorithms, networks, geometric applications, and string.

---

Table of contents :
Front Matter….Pages –
Modeling and Analyzing Massive Terrain Data Sets….Pages 1-1
Coloring Triangle-Free Graphs on Surfaces….Pages 2-4
Integer Representation and Counting in the Bit Probe Model….Pages 5-16
Minimum Degree Orderings….Pages 17-28
Greedy Approximation for Source Location Problem with Vertex-Connectivity Requirements in Undirected Graphs….Pages 29-40
Dynamic Distance Hereditary Graphs Using Split Decomposition….Pages 41-51
Unifying Two Graph Decompositions with Modular Decomposition….Pages 52-64
Escaping Off-Line Searchers and a Discrete Isoperimetric Theorem….Pages 65-74
Geometric Spanner of Segments….Pages 75-87
Dilation-Optimal Edge Deletion in Polygonal Cycles….Pages 88-99
Unbounded-Error Classical and Quantum Communication Complexity….Pages 100-111
A Spectral Method for MAX2SAT in the Planted Solution Model….Pages 112-123
On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices….Pages 124-136
The 1-Versus-2 Queries Problem Revisited….Pages 137-147
Approximating the Crossing Number of Toroidal Graphs….Pages 148-159
Width-Optimal Visibility Representations of Plane Graphs….Pages 160-171
Computing Upward Topological Book Embeddings of Upward Planar Digraphs….Pages 172-183
Algorithms for the Hypergraph and the Minor Crossing Number Problems….Pages 184-195
On Mixing and Edge Expansion Properties in Randomized Broadcasting….Pages 196-207
Linear Reconfiguration of Cube-Style Modular Robots….Pages 208-219
Fast Message Dissemination in Random Geometric Ad-Hoc Radio Networks….Pages 220-231
Sensor Network Gossiping or How to Break the Broadcast Lower Bound….Pages 232-243
On the Complexity of the “Most General” Undirected Firing Squad Synchronization Problem….Pages 244-255
Capacitated Domination Problem….Pages 256-267
The Complexity of Finding Subgraphs Whose Matching Number Equals the Vertex Cover Number….Pages 268-279
New Bounds for the Nearly Equitable Edge Coloring Problem….Pages 280-291
Approximation to the Minimum Cost Edge Installation Problem….Pages 292-303
Approximability of Packing Disjoint Cycles….Pages 304-315
Succinct Representation of Labeled Graphs….Pages 316-328
More Efficient Algorithms and Analyses for Unequal Letter Cost Prefix-Free Coding….Pages 329-340
Kinetic Maintenance of Mobile k-Centres on Trees….Pages 341-352
Checking Value-Sensitive Data Structures in Sublinear Space….Pages 353-364
Manipulation in Games….Pages 365-376
Using Nash Implementation to Achieve Better Frugality Ratios….Pages 377-389
The Price of Nash Equilibria in Multicast Transmissions Games….Pages 390-401
An Efficient Algorithm for Enumerating Pseudo Cliques….Pages 402-414
Fast Adaptive Diagnosis with a Minimum Number of Tests….Pages 415-426
Dynamic Structures for Top- k Queries on Uncertain Data….Pages 427-438
Separating Populations with Wide Data: A Spectral Analysis….Pages 439-451
A Constant-Competitive Algorithm for Online OVSF Code Assignment….Pages 452-463
Average-Case Analysis of Online Topological Ordering….Pages 464-475
Energy Efficient Deadline Scheduling in Two Processor Systems….Pages 476-487
On the Relative Dominance of Paging Algorithms….Pages 488-499
I/O-Efficient Map Overlay and Point Location in Low-Density Subdivisions….Pages 500-511
Geometric Streaming Algorithms with a Sorting Primitive….Pages 512-524
External Memory Range Reporting on a Grid….Pages 525-535
Approximate Range Searching in External Memory….Pages 536-548
Faster Treasure Hunt and Better Strongly Universal Exploration Sequences….Pages 549-560
Hardness and Approximation of Traffic Grooming….Pages 561-573
Depth of Field and Cautious-Greedy Routing in Social Networks….Pages 574-586
Locating Facilities on a Network to Minimize Their Average Service Radius….Pages 587-598
Faster Combinatorial Algorithms for Determinant and Pfaffian….Pages 599-608
A Polynomial-Time-Delay and Polynomial-Space Algorithm for Enumeration Problems in Multi-criteria Optimization….Pages 609-620
The Parameterized Complexity of the Unique Coverage Problem….Pages 621-631
Bounded Tree-Width and CSP-Related Problems….Pages 632-643
Covering Points by Unit Disks of Fixed Location….Pages 644-655
Geodesic Disks and Clustering in a Simple Polygon….Pages 656-667
An O ( n 2 log n ) Time Algorithm for Computing Shortest Paths Amidst Growing Discs in the Plane….Pages 668-680
Optimal Triangulation with Steiner Points….Pages 681-691
New Algorithm for Field Splitting in Radiation Therapy….Pages 692-703
In-Place Algorithm for Image Rotation….Pages 704-715
Higher Order Voronoi Diagrams of Segments for VLSI Critical Area Extraction….Pages 716-727
Distributed Relationship Schemes for Trees….Pages 728-738
Fast Evaluation of Union-Intersection Expressions….Pages 739-750
A Sub-cubic Time Algorithm for the k -Maximum Subarray Problem….Pages 751-762
Compressing Spatio-temporal Trajectories….Pages 763-775
Finding Popular Places….Pages 776-787
Maintaining Extremal Points and Its Applications to Deciding Optimal Orientations….Pages 788-799
The Monomial Ideal Membership Problem and Polynomial Identity Testing….Pages 800-811
On the Fault Testing for Reversible Circuits….Pages 812-821
The Space Complexity of k -Tree Isomorphism….Pages 822-833
Algorithms for Computing the Length-Constrained Max-Score Segments with Applications to DNA Copy Number Data Analysis….Pages 834-845
Space Efficient Indexes for String Matching with Don’t Cares….Pages 846-857
2-Stage Fault Tolerant Interval Group Testing….Pages 858-868
Approximate String Matching with Swap and Mismatch….Pages 869-880
Minimum Fill-In and Treewidth of Split+  ke and Split+  kv Graphs….Pages 881-892
Weighted Treewidth Algorithmic Techniques and Results….Pages 893-903
Spanning Trees with Many Leaves in Regular Bipartite Graphs….Pages 904-914
Problem Kernels for NP-Complete Edge Deletion Problems: Split and Related Graphs….Pages 915-926
Back Matter….Pages –