Algorithms and Computation: 13th International Symposium, ISAAC 2002 Vancouver, BC, Canada, November 21–23, 2002 Proceedings

Amitabha Bagchi, Adam L. Buchsbaum, Michael T. Goodrich (auth.), Prosenjit Bose, Pat Morin (eds.)3540001425, 9783540001423

This book constitutes the refereed proceedings of the 13th Annual International Symposium on Algorithms and Computation, ISAAC 2002, held in Vancouver, BC, Canada in November 2002.

The 54 revised full papers presented together with 3 invited contributions were carefully reviewed and selected from close to 160 submissions. The papers cover all relevant topics in algorithmics and computation, in particular computational geometry, algorithms and data structures, approximation algorithms, randomized algorithms, graph drawing and graph algorithms, combinatorial optimization, computational biology, computational finance, cryptography, and parallel and distributedd algorithms.

---

Table of contents :
Biased Skip Lists….Pages 1-13
Space-Efficient Data Structures for Flexible Text Retrieval Systems….Pages 14-24
Key Independent Optimality….Pages 25-31
On the Comparison-Addition Complexity of All-Pairs Shortest Paths….Pages 32-43
On the Clique-Width of Graphs in Hereditary Classes….Pages 44-54
The Probability of a Rendezvous Is Minimal in Complete Graphs….Pages 55-66
On the Minimum Volume of a Perturbed Unit Cube….Pages 67-78
Non-Delaunay-Based Curve Reconstruction….Pages 79-90
Cutting a Country for Smallest Square Fit….Pages 91-102
On the Emptiness Problem for Two-Way NFA with One Reversal-Bounded Counter….Pages 103-114
Quantum Multi-prover Interactive Proof Systems with Limited Prior Entanglement….Pages 115-127
Some Remarks on the L -Conjecture….Pages 128-136
A Framework for Network Reliability Problems on Graphs of Bounded Treewidth….Pages 137-149
A Faster Approximation Algorithm for 2-Edge-Connectivity Augmentation….Pages 150-162
Tree Spanners on Chordal Graphs: Complexity, Algorithms, Open Problems….Pages 163-174
An Asymptotic Fully Polynomial Time Approximation Scheme for Bin Covering….Pages 175-186
Improved Approximation Algorithms for Max-2SAT with Cardinality Constraint….Pages 187-198
A Better Approximation for the Two-Stage Assembly Scheduling Problem with Two Machines at the First Stage….Pages 199-210
Queaps….Pages 211-218
Funnel Heap-A Cache Oblivious Priority Queue….Pages 219-228
Characterizing History Independent Data Structures….Pages 229-240
Faster Fixed Parameter Tractable Algorithms for Undirected Feedback Vertex Set….Pages 241-248
An O ( pn + 1.151 p )-Algorithm for p -Profit Cover and Its Practical Implications for Vertex Cover….Pages 249-261
Exponential Speedup of Fixed-Parameter Algorithms on K 3,3 -Minor-Free or K 5 -Minor-Free Graphs….Pages 262-273
Casting a Polyhedron with Directional Uncertainty….Pages 274-285
Hierarchy of Surface Models and Irreducible Triangulation….Pages 286-295
Algorithms and Complexity for Tetrahedralization Detections….Pages 296-307
Average-Case Communication-Optimal Parallel Parenthesis Matching….Pages 308-319
Optimal F -Reliable Protocols for the Do-All Problem on Single-Hop Wireless Networks….Pages 320-331
New Results for Energy-Efficient Broadcasting in Wireless Networks….Pages 332-343
An Improved Algorithm for the Minimum Manhattan Network Problem….Pages 344-356
Approximate Distance Oracles Revisited….Pages 357-368
Flat-State Connectivity of Linkages under Dihedral Motions….Pages 369-380
Project Scheduling with Irregular Costs: Complexity, Approximability, and Algorithms….Pages 381-390
Scheduling of Independent Dedicated Multiprocessor Tasks….Pages 391-402
On the Approximability of Multiprocessor Task Scheduling Problems….Pages 403-415
Bounded-Degree Independent Sets in Planar Graphs….Pages 416-427
Minimum Edge Ranking Spanning Trees of Threshold Graphs….Pages 428-440
File Transfer Tree Problems….Pages 441-452
Approximation Algorithms for Some Parameterized Counting Problems….Pages 453-464
Approximating MIN k -SAT….Pages 465-475
Average-Case Competitive Analyses for Ski-Rental Problems….Pages 476-488
On the Clique Problem in Intersection Graphs of Ellipses….Pages 489-500
A Geometric Approach to Boolean Matrix Multiplication….Pages 501-510
The Min-Max Voronoi Diagram of Polygons and Applications in VLSI Manufacturing….Pages 511-522
Improved Distance Oracles for Avoiding Link-Failure….Pages 523-534
Probabilistic Algorithms for the Wakeup Problem in Single-Hop Radio Networks….Pages 535-549
A Simple, Memory-Efficient Bounded Concurrent Timestamping Algorithm….Pages 550-562
Crossing Minimization for Symmetries….Pages 563-574
Simultaneous Embedding of a Planar Graph and Its Dual on the Grid….Pages 575-587
Meaningful Information….Pages 588-599
Optimal Clearing of Supply/Demand Curves….Pages 600-611
Partitioning Trees of Supply and Demand….Pages 612-623
Maximizing a Voronoi Region: The Convex Case….Pages 624-634
Random Tries….Pages 635-635
Expected Acceptance Counts for Finite Automata with Almost Uniform Input….Pages 636-646
Monotone Drawings of Planar Graphs….Pages 647-653