Algorithms and Computation

Table of Contents

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