Algorithms and Computation [electronic resource] : 13th International Symposium, ISAAC 2002 Vancouver, BC, Canada, November 21-23, 2002, Proceedings /

Session 1A -- Biased Skip Lists -- Space-Efficient Data Structures for Flexible Text Retrieval Systems -- Key Independent Optimality -- On the Comparison-Addition Complexity of All-Pairs Shortest Paths -- On the Comparison-Addition Complexity of All-Pairs Shortest Paths -- On the Clique-Width of Graphs in Hereditary Classes -- On the Clique-Width of Graphs in Hereditary Classes -- The Probability of a Rendezvous Is Minimal in Complete Graphs -- The Probability of a Rendezvous Is Minimal in Complete Graphs -- On the Minimum Volume of a Perturbed Unit Cube -- On the Minimum Volume of a Perturbed Unit Cube -- Non-Delaunay-Based Curve Reconstruction -- Non-Delaunay-Based Curve Reconstruction -- Cutting a Country for Smallest Square Fit -- Cutting a Country for Smallest Square Fit -- On the Emptiness Problem for Two-Way NFA with One Reversal-Bounded Counter -- On the Emptiness Problem for Two-Way NFA with One Reversal-Bounded Counter -- Quantum Multi-prover Interactive Proof Systems with Limited Prior Entanglement -- Quantum Multi-prover Interactive Proof Systems with Limited Prior Entanglement -- Some Remarks on the L-Conjecture -- Some Remarks on the L-Conjecture -- Session 3A -- A Framework for Network Reliability Problems on Graphs of Bounded Treewidth -- A Faster Approximation Algorithm for 2-Edge-Connectivity Augmentation -- Tree Spanners on Chordal Graphs: Complexity, Algorithms, Open Problems -- Session 3B -- An Asymptotic Fully Polynomial Time Approximation Scheme for Bin Covering -- Improved Approximation Algorithms for Max-2SAT with Cardinality Constraint -- A Better Approximation for the Two-Stage Assembly Scheduling Problem with Two Machines at the First Stage -- Session 4A -- Queaps -- Funnel Heap-A Cache Oblivious Priority Queue -- Characterizing History Independent Data Structures -- Session4B -- Faster Fixed Parameter Tractable Algorithms for Undirected Feedback Vertex Set -- An O(pn + 1.151p)-Algorithm for p-Profit Cover and Its Practical Implications for Vertex Cover -- Exponential Speedup of Fixed-Parameter Algorithms on K 3,3-Minor-Free or K 5-Minor-Free Graphs -- Session 5A -- Casting a Polyhedron with Directional Uncertainty -- Hierarchy of Surface Models and Irreducible Triangulation -- Algorithms and Complexity for Tetrahedralization Detections -- Session 5B -- Average-Case Communication-Optimal Parallel Parenthesis Matching -- Optimal F-Reliable Protocols for the Do-All Problem on Single-Hop Wireless Networks -- New Results for Energy-Efficient Broadcasting in Wireless Networks -- Session 6A -- An Improved Algorithm for the Minimum Manhattan Network Problem -- Approximate Distance Oracles Revisited -- Flat-State Connectivity of Linkages under Dihedral Motions -- Session 6B -- Project Scheduling with Irregular Costs: Complexity, Approximability, and Algorithms -- Scheduling of Independent Dedicated Multiprocessor Tasks -- On the Approximability of Multiprocessor Task Scheduling Problems -- Session 7A -- Bounded-Degree Independent Sets in Planar Graphs -- Minimum Edge Ranking Spanning Trees of Threshold Graphs -- File Transfer Tree Problems -- Session 7B -- Approximation Algorithms for Some Parameterized Counting Problems -- Approximating MIN k-SAT -- Average-Case Competitive Analyses for Ski-Rental Problems -- Session 8A -- On the Clique Problem in Intersection Graphs of Ellipses -- A Geometric Approach to Boolean Matrix Multiplication -- The Min-Max Voronoi Diagram of Polygons and Applications in VLSI Manufacturing -- Session 8B -- Improved Distance Oracles for Avoiding Link-Failure -- Probabilistic Algorithms for the Wakeup Problem in Single-Hop Radio Networks -- A Simple, Memory-Efficient Bounded Concurrent Timestamping Algorithm -- Session 9A -- Crossing Minimization for Symmetries -- Simultaneous Embedding of a Planar Graph and Its Dual on the Grid -- Meaningful Information -- Session 9B -- Optimal Clearing of Supply/Demand Curves -- Partitioning Trees of Supply and Demand -- Maximizing a Voronoi Region: The Convex Case -- Invited Talks -- Random Tries -- Expected Acceptance Counts for Finite Automata with Almost Uniform Input -- Monotone Drawings of Planar Graphs.