Algorithms and Computation

Table of Contents

1. Altmetric Badge
   Book Overview
2. Altmetric Badge
   Chapter 1 Algorithmic Problems in Wireless Ad Hoc Networks
3. Altmetric Badge
   Chapter 2 Probability and Recursion
4. Altmetric Badge
   Chapter 3 Embedding Point Sets into Plane Graphs of Small Dilation
5. Altmetric Badge
   Chapter 4 The Layered Net Surface Problems in Discrete Geometry and Medical Image Segmentation
6. Altmetric Badge
   Chapter 5 Separability with Outliers
7. Altmetric Badge
   Chapter 6 Casting an Object with a Core
8. Altmetric Badge
   Chapter 7 Sparse Geometric Graphs with Small Dilation
9. Altmetric Badge
   Chapter 8 Multiple Polyline to Polygon Matching
10. Altmetric Badge
    Chapter 9 Minimizing a Monotone Concave Function with Laminar Covering Constraints
11. Altmetric Badge
    Chapter 10 Almost Optimal Solutions for Bin Coloring Problems
12. Altmetric Badge
    Chapter 11 GEN-LARAC: A Generalized Approach to the Constrained Shortest Path Problem Under Multiple Additive Constraints
13. Altmetric Badge
    Chapter 12 Simultaneous Matchings
14. Altmetric Badge
    Chapter 13 An Optimization Problem Related to VoD Broadcasting
15. Altmetric Badge
    Chapter 14 A Min-Max Relation on Packing Feedback Vertex Sets
16. Altmetric Badge
    Chapter 15 Average Case Analysis for Tree Labelling Schemes
17. Altmetric Badge
    Chapter 16 Revisiting T. Uno and M. Yagiura’s Algorithm
18. Altmetric Badge
    Chapter 17 Generating Cut Conjunctions and Bridge Avoiding Extensions in Graphs
19. Altmetric Badge
    Chapter 18 Orthogonal Drawings of Series-Parallel Graphs with Minimum Bends
20. Altmetric Badge
    Chapter 19 Bisecting a Four-Connected Graph with Three Resource Sets
21. Altmetric Badge
    Chapter 20 Laminar Structure of Ptolemaic Graphs and Its Applications
22. Altmetric Badge
    Chapter 21 On the Complexity of the G -Reconstruction Problem
23. Altmetric Badge
    Chapter 22 Hybrid Voting Protocols and Hardness of Manipulation
24. Altmetric Badge
    Chapter 23 On the Complexity of Rocchio’s Similarity-Based Relevance Feedback Algorithm
25. Altmetric Badge
    Chapter 24 Correlation Clustering and Consensus Clustering
26. Altmetric Badge
    Chapter 25 An Approximation Algorithm for Scheduling Malleable Tasks Under General Precedence Constraints
27. Altmetric Badge
    Chapter 26 A 1.5-Approximation of the Minimal Manhattan Network Problem
28. Altmetric Badge
    Chapter 27 Hardness and Approximation of Octilinear Steiner Trees
29. Altmetric Badge
    Chapter 28 Dense Subgraph Problems with Output-Density Conditions
30. Altmetric Badge
    Chapter 29 A Complete Characterization of Tolerable Adversary Structures for Secure Point-to-Point Transmissions Without Feedback
31. Altmetric Badge
    Chapter 30 Network Game with Attacker and Protector Entities
32. Altmetric Badge
    Chapter 31 SkipTree: A Scalable Range-Queryable Distributed Data Structure for Multidimensional Data
33. Altmetric Badge
    Chapter 32 The Phase Matrix
34. Altmetric Badge
    Chapter 33 ISB-Tree: A New Indexing Scheme with Efficient Expected Behaviour
35. Altmetric Badge
    Chapter 34 External Data Structures for Shortest Path Queries on Planar Digraphs
36. Altmetric Badge
    Chapter 35 Improved Approximate String Matching Using Compressed Suffix Data Structures
37. Altmetric Badge
    Chapter 36 Algorithms and Computation
38. Altmetric Badge
    Chapter 37 Approximate Colored Range Queries
39. Altmetric Badge
    Chapter 38 Complexity and Approximation of the Minimum Recombination Haplotype Configuration Problem
40. Altmetric Badge
    Chapter 39 Space Efficient Algorithms for Ordered Tree Comparison
41. Altmetric Badge
    Chapter 40 A 1.75-Approximation Algorithm for Unsigned Translocation Distance
42. Altmetric Badge
    Chapter 41 Fast Algorithms for Computing the Tripartition-Based Distance Between Phylogenetic Networks
43. Altmetric Badge
    Chapter 42 Improved Algorithms for Largest Cardinality 2-Interval Pattern Problem
44. Altmetric Badge
    Chapter 43 Preemptive Semi-online Scheduling on Parallel Machines with Inexact Partial Information
45. Altmetric Badge
    Chapter 44 On-Line Computation and Maximum-Weighted Hereditary Subgraph Problems
46. Altmetric Badge
    Chapter 45 A Novel Adaptive Learning Algorithm for Stock Market Prediction
47. Altmetric Badge
    Chapter 46 Uniformization of Discrete Data
48. Altmetric Badge
    Chapter 47 A Practical Algorithm for the Computation of Market Equilibrium with Logarithmic Utility Functions
49. Altmetric Badge
    Chapter 48 Boosting Spectral Partitioning by Sampling and Iteration
50. Altmetric Badge
    Chapter 49 Smoothed Analysis of Binary Search Trees
51. Altmetric Badge
    Chapter 50 Simple and Efficient Greedy Algorithms for Hamilton Cycles in Random Intersection Graphs
52. Altmetric Badge
    Chapter 51 Counting Distinct Items over Update Streams
53. Altmetric Badge
    Chapter 52 Randomized Algorithm for the Sum Selection Problem
54. Altmetric Badge
    Chapter 53 An Improved Interval Routing Scheme for Almost All Networks Based on Dominating Cliques
55. Altmetric Badge
    Chapter 54 Basic Computations in Wireless Networks
56. Altmetric Badge
    Chapter 55 A Simple Optimal Randomized Algorithm for Sorting on the PDM
57. Altmetric Badge
    Chapter 56 Efficient Parallel Algorithms for Constructing a k -Tree Center and a k -Tree Core of a Tree Network
58. Altmetric Badge
    Chapter 57 A Tight Bound on the Number of Mobile Servers to Guarantee the Mutual Transferability Among Dominating Configurations
59. Altmetric Badge
    Chapter 58 Bounding the Number of Minimal Dominating Sets: A Measure and Conquer Approach
60. Altmetric Badge
    Chapter 59 Collective Tree Spanners in Graphs with Bounded Genus, Chordality, Tree-Width, or Clique-Width
61. Altmetric Badge
    Chapter 60 Sampling Unlabeled Biconnected Planar Graphs
62. Altmetric Badge
    Chapter 61 Configurations with Few Crossings in Topological Graphs
63. Altmetric Badge
    Chapter 62 On Bounded Load Routings for Modeling k -Regular Connection Topologies
64. Altmetric Badge
    Chapter 63 On the Complexity of Global Constraint Satisfaction
65. Altmetric Badge
    Chapter 64 Polynomial Space Suffices for Deciding Nash Equilibria Properties for Extensive Games with Large Trees,
66. Altmetric Badge
    Chapter 65 An Improved $\tilde{\mathcal{O}}(1.234^{m})$ -Time Deterministic Algorithm for SAT
67. Altmetric Badge
    Chapter 66 Solving Minimum Weight Exact Satisfiability in Time O (2 0.2441 n )
68. Altmetric Badge
    Chapter 67 Efficient Algorithms for Finding a Longest Common Increasing Subsequence
69. Altmetric Badge
    Chapter 68 Decision Making Based on Approximate and Smoothed Pareto Curves
70. Altmetric Badge
    Chapter 69 Computing Optimal Solutions for the min 3-set covering Problem
71. Altmetric Badge
    Chapter 70 Efficient Algorithms for the Weighted 2-Center Problem in a Cactus Graph
72. Altmetric Badge
    Chapter 71 Algorithms for Local Forest Similarity
73. Altmetric Badge
    Chapter 72 Fast Algorithms for Finding Disjoint Subsequences with Extremal Densities
74. Altmetric Badge
    Chapter 73 A Polynomial Space and Polynomial Delay Algorithm for Enumeration of Maximal Motifs in a Sequence
75. Altmetric Badge
    Chapter 74 5-th Phylogenetic Root Construction for Strictly Chordal Graphs
76. Altmetric Badge
    Chapter 75 Recursion Theoretic Operators for Function Complexity Classes
77. Altmetric Badge
    Chapter 76 From Balls and Bins to Points and Vertices
78. Altmetric Badge
    Chapter 77 Simulating Undirected st -Connectivity Algorithms on Uniform JAGs and NNJAGs
79. Altmetric Badge
    Chapter 78 Upper Bounds on the Computational Power of an Optical Model of Computation
80. Altmetric Badge
    Chapter 79 Complexity of the Min-Max (Regret) Versions of Cut Problems
81. Altmetric Badge
    Chapter 80 Improved Algorithms for the k Maximum-Sums Problems
82. Altmetric Badge
    Chapter 81 Network Load Games
83. Altmetric Badge
    Chapter 82 Minimum Entropy Coloring
84. Altmetric Badge
    Chapter 83 Algorithms for Max Hamming Exact Satisfiability
85. Altmetric Badge
    Chapter 84 Counting Stable Strategies in Random Evolutionary Games
86. Altmetric Badge
    Chapter 85 Exact and Approximation Algorithms for Computing the Dilation Spectrum of Paths, Trees, and Cycles
87. Altmetric Badge
    Chapter 86 On the Computation of Colored Domino Tilings of Simple and Non-simple Orthogonal Polygons
88. Altmetric Badge
    Chapter 87 Optimal Paths for Mutually Visible Agents
89. Altmetric Badge
    Chapter 88 Stacking and Bundling Two Convex Polygons
90. Altmetric Badge
    Chapter 89 Algorithms for Range-Aggregate Query Problems Involving Geometric Aggregation Operations
91. Altmetric Badge
    Chapter 90 A ( $2 - c{{1} \over {\sqrt{N}}}$ )–Approximation Algorithm for the Stable Marriage Problem
92. Altmetric Badge
    Chapter 91 Approximating the Traffic Grooming Problem
93. Altmetric Badge
    Chapter 92 Scheduling to Minimize Makespan with Time-Dependent Processing Times
94. Altmetric Badge
    Chapter 93 On Complexity and Approximability of the Labeled Maximum/Perfect Matching Problems
95. Altmetric Badge
    Chapter 94 Finding a Weight-Constrained Maximum-Density Subtree in a Tree
96. Altmetric Badge
    Chapter 95 Finding Two Disjoint Paths in a Network with Normalized α  +  -MIN-SUM Objective Function
97. Altmetric Badge
    Chapter 96 Sensitivity Analysis of Minimum Spanning Trees in Sub-inverse-Ackermann Time
98. Altmetric Badge
    Chapter 97 Approximation Algorithms for Layered Multicast Scheduling
99. Altmetric Badge
    Chapter 98 Minimum Weight Triangulation by Cutting Out Triangles
100. Altmetric Badge
     Chapter 99 Multi-directional Width-Bounded Geometric Separator and Protein Folding
101. Altmetric Badge
     Chapter 100 Shortest Paths and Voronoi Diagrams with Transportation Networks Under General Distances
102. Altmetric Badge
     Chapter 101 Approximation Algorithms for Computing the Earth Mover’s Distance Under Transformations
103. Altmetric Badge
     Chapter 102 Fast k-Means Algorithms with Constant Approximation
104. Altmetric Badge
     Chapter 103 On Efficient Weighted Rectangle Packing with Large Resources
105. Altmetric Badge
     Chapter 104 On Routing in VLSI Design and Communication Networks
106. Altmetric Badge
     Chapter 105 The Capacitated Traveling Salesman Problem with Pickups and Deliveries on a Tree
107. Altmetric Badge
     Chapter 106 Distance Labeling in Hyperbolic Graphs
108. Altmetric Badge
     Chapter 107 Multi-source Trees: Algorithms for Minimizing Eccentricity Cost Metrics
109. Altmetric Badge
     Chapter 108 Edge-Pancyclicity of Twisted Cubes
110. Altmetric Badge
     Chapter 109 Combinatorial Network Abstraction by Trees and Distances
111. Altmetric Badge
     Chapter 110 Drawing Phylogenetic Trees
112. Altmetric Badge
     Chapter 111 Localized and Compact Data-Structure for Comparability Graphs
113. Altmetric Badge
     Chapter 112 Representation of Graphs by OBDDs
114. Altmetric Badge
     Chapter 113 Space-Efficient Construction of LZ-Index
115. Altmetric Badge
     Chapter 114 Longest Increasing Subsequences in Windows Based on Canonical Antichain Partition
116. Altmetric Badge
     Chapter 115 Pareto Optimality in House Allocation Problems
117. Altmetric Badge
     Chapter 116 Generalized Geometric Approaches for Leaf Sequencing Problems in Radiation Therapy,