Algorithms and Computation: 15th International Symposium, ISAAC 2004, Hong Kong, China, December 20-22, 2004. Proceedings

Front Matter....Pages -
Puzzles, Art, and Magic with Algorithms....Pages 1-1
The ABCs of AVDs: Geometric Retrieval Made Simple....Pages 2-2
Pareto Optimality in House Allocation Problems....Pages 3-15
Property-Preserving Data Reconstruction....Pages 16-27
On the Monotone Circuit Complexity of Quadratic Boolean Functions....Pages 28-40
Generalized Function Matching....Pages 41-52
Approximate Distance Oracles for Graphs with Dense Clusters....Pages 53-64
Multicriteria Global Minimum Cuts....Pages 65-76
Polyline Fitting of Planar Points Under Min-sum Criteria....Pages 77-88
A Generalization of Magic Squares with Applications to Digital Halftoning....Pages 89-100
Voronoi Diagrams with a Transportation Network on the Euclidean Plane....Pages 101-112
Structural Alignment of Two RNA Sequences with Lagrangian Relaxation....Pages 113-123
Poly-APX- and PTAS-Completeness in Standard and Differential Approximation....Pages 124-136
Efficient Algorithms for k Maximum Sums....Pages 137-148
Equipartitions of Measures by 2-Fans....Pages 149-158
Augmenting the Edge-Connectivity of a Spider Tree....Pages 159-171
On Nash Equilibria for Multicast Transmissions in Ad-Hoc Wireless Networks....Pages 172-183
Structural Similarity in Graphs....Pages 184-195
Flexibility of Steiner Trees in Uniform Orientation Metrics....Pages 196-208
Random Access to Advice Strings and Collapsing Results....Pages 209-220
Bounding the Payment of Approximate Truthful Mechanisms....Pages 221-233
The Polymatroid Steiner Problems....Pages 234-245
Geometric Optimization Problems Over Sliding Windows....Pages 246-258
On-Line Windows Scheduling of Temporary Items....Pages 259-270
Generalized Geometric Approaches for Leaf Sequencing Problems in Radiation Therapy....Pages 271-281
An Efficient Exact Algorithm for the Minimum Ultrametric Tree Problem....Pages 282-293
On the Range Maximum-Sum Segment Query Problem....Pages 294-305
An Efficient Algorithm for Finding Maximum Cycle Packings in Reducible Flow Graphs....Pages 306-317
Efficient Job Scheduling Algorithms with Multi-type Contentions....Pages 318-329
Superimposing Voronoi Complexes for Shape Deformation....Pages 330-341
On Partial Lifting and the Elliptic Curve Discrete Logarithm Problem....Pages 342-351
Guarding Art Galleries by Guarding Witnesses....Pages 352-363
On p -Norm Based Locality Measures of Space-Filling Curves....Pages 364-376
Composability of Infinite-State Activity Automata....Pages 377-388
Error Compensation in Leaf Root Problems....Pages 389-401
On Compact and Efficient Routing in Certain Graph Classes....Pages 402-414
Randomized Insertion and Deletion in Point Quad Trees....Pages 415-426
Diagnosis in the Presence of Intermittent Faults....Pages 427-441
Three-Round Adaptive Diagnosis in Binary n -Cubes....Pages 442-451
Fast Algorithms for Comparison of Similar Unordered Trees....Pages 452-463
GCD of Random Linear Forms....Pages 464-469
On the Hardness and Easiness of Random 4-SAT Formulas....Pages 470-483
Minimum Common String Partition Problem: Hardness and Approximations....Pages 484-495
On the Complexity of Network Synchronization....Pages 496-507
Counting Spanning Trees and Other Structures in Non-constant-jump Circulant Graphs....Pages 508-521
Adaptive Spatial Partitioning for Multidimensional Data Streams....Pages 522-533
Paired Pointset Traversal....Pages 534-544
Approximated Two Choices in Randomized Load Balancing....Pages 545-557
Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting....Pages 558-568
Local Gapped Subforest Alignment and Its Application in Finding RNA Structural Motifs....Pages 569-580
The Maximum Agreement of Two Nested Phylogenetic Networks....Pages 581-593
Sequences of Radius k : How to Fetch Many Huge Objects into Small Memory for Pairwise Computations....Pages 594-605
New Bounds on Map Labeling with Circular Labels....Pages 606-617
Optimal Buffer Management via Resource Augmentation....Pages 618-628
Oriented Paths in Mixed Graphs....Pages 629-643
Polynomial Deterministic Rendezvous in Arbitrary Graphs....Pages 644-656
Distributions of Points and Large Quadrangles....Pages 657-668
Cutting Out Polygons with Lines and Rays....Pages 669-680
Advantages of Backward Searching — Efficient Secondary Memory and Distributed Implementation of Compressed Suffix Arrays....Pages 681-692
Inner Rectangular Drawings of Plane Graphs....Pages 693-704
Approximating the Minmax Subtree Cover Problem in a Cactus....Pages 705-716
Boundary-Optimal Triangulation Flooding....Pages 717-728
Exact Computation of Polynomial Zeros Expressible by Square Roots....Pages 729-741
Many-to-Many Disjoint Path Covers in a Graph with Faulty Elements....Pages 742-753
An O ( n log n )-Time Algorithm for the Maximum Constrained Agreement Subtree Problem for Binary Trees....Pages 754-765
Planning the Transportation of Multiple Commodities in Bidirectional Pipeline Networks....Pages 766-777
Efficient Algorithms for the Hotlink Assignment Problem: The Worst Case Search....Pages 778-792
Dynamic Tree Cross Products....Pages 793-804
Spanners, Weak Spanners, and Power Spanners for Wireless Networks....Pages 805-821
Techniques for Indexing and Querying Temporal Observations for a Collection of Objects....Pages 822-834
Approximation Algorithms for the Consecutive Ones Submatrix Problem on Sparse Matrices....Pages 835-846
The Two-Guard Problem Revisited and Its Generalization....Pages 847-858
Canonical Data Structure for Interval Probe Graphs....Pages 859-870
Efficient Algorithms for the Longest Path Problem....Pages 871-883
Randomized Algorithms for Motif Detection....Pages 884-895
Weighted Coloring on Planar, Bipartite and Split Graphs: Complexity and Improved Approximation....Pages 896-907
Sweeping Graphs with Large Clique Number....Pages 908-920
A Slightly Improved Sub-cubic Algorithm for the All Pairs Shortest Paths Problem with Real Edge Lengths....Pages 921-932
Back Matter....Pages -