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

Morin, Pat; Bose, Prosenjit

Brossura

ISBN 10: 3540001425 ISBN 13: 9783540001423

Casa editrice: Springer, 2008

Riassunto

No conference can succeed without exceptional local organization. For the often overlooked and thankless task of ?nding a suitable venue and banquet location,dealingwiththelogisticsofregistration,organizinglunchesandco?ee, etc.,wewouldliketothankthetheorganizingcommittee,NadjaRence,andOlga Stachova for all their e?orts above and beyond the call of duty. We thank our sponsorsSimonFraserUniversity,thePaci?cInstituteofMathematicalSciences, the institute for Mathematics of Information Technology and Complex Systems, andBajaiInc.fortheirgeneroussupport.Finally,wethankalltheauthorsand participants. We hope this edition of ISAAC will be a success.

Su questo libro

Contenuti

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.- Session 4B.- 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.

Dettagli dell?edizione

• Editore: Springer
• Data di pubblicazione: 2008
• ISBN 10: 3540001425
• ISBN 13: 9783540001423
• Rilegatura: Copertina flessibile
• Lingua: Inglese
• Numero di pagine: 676
• Contatto del produttore: non disponibile