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

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