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

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 -