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

Erik D. Demaine (auth.), Rudolf Fleischer, Gerhard Trippen (eds.)9783540241317, 3540241310

This volume contains the proceedings of the 15th Annual International Sym- sium on Algorithms and Computation (ISAAC 2004), held in Hong Kong, 20–22 December, 2004. In the past, it has been held in Tokyo (1990), Taipei (1991), Nagoya (1992), Hong Kong (1993), Beijing (1994), Cairns (1995), Osaka (1996), Singapore (1997), Taejon (1998), Chennai (1999), Taipei (2000), Christchurch (2001), Vancouver (2002), and Kyoto (2003). ISAAC is an annual international symposium that covers a wide range of topics,namelyalgorithmsandcomputation.Themainpurposeofthesymposium is to provide a forum for researchers working in the active research community of algorithms and the theory of computation to present and exchange new ideas. In response to our call for papers we received 226 submissions. The task of selectingthepapersinthisvolumewasdonebyourprogramcommitteeandother referees. After a thorough review process the committee selected 76 papers, the decisions being based on originality and relevance to the ?eld of algorithms and computation. We hope all accepted papers will eventually appear in scienti?c journals in a more polished form. Two special issues, one of Algorithmica and one of the International Journal of Computational Geometry and Applications, with selected papers from ISAAC 2004 are in preparation. Thebeststudentpaperawardwillbegivenfor“Geometricoptimizationpr- lems over sliding windows” by Bashir S. Sadjad and Timothy M. Chan from the University of Waterloo. Two eminent invited speakers, Prof. Erik D. Demaine, MIT, and Prof. David M. Mount, University of Maryland, also contributed to this volume.

---

Table of contents :
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 –