%PDF-1.5 % 1 0 obj << /S /GoTo /D (chapter.1) >> endobj 4 0 obj (Introduction) endobj 5 0 obj << /S /GoTo /D (section.1.1) >> endobj 8 0 obj (Preliminaries) endobj 9 0 obj << /S /GoTo /D (section.1.2) >> endobj 12 0 obj (Overview of Results) endobj 13 0 obj << /S /GoTo /D (subsection.1.2.1) >> endobj 16 0 obj (Connectivity Data Structures) endobj 17 0 obj << /S /GoTo /D (subsection.1.2.2) >> endobj 20 0 obj (Network Design) endobj 21 0 obj << /S /GoTo /D (part.1) >> endobj 24 0 obj (I Connectivity Data Structures) endobj 25 0 obj << /S /GoTo /D (chapter.2) >> endobj 28 0 obj (Cactus Construction) endobj 29 0 obj << /S /GoTo /D (section.2.1) >> endobj 32 0 obj (Background) endobj 33 0 obj << /S /GoTo /D (subsection.2.1.1) >> endobj 36 0 obj (History) endobj 37 0 obj << /S /GoTo /D (subsection.2.1.2) >> endobj 40 0 obj (Our Contributions) endobj 41 0 obj << /S /GoTo /D (subsection.2.1.3) >> endobj 44 0 obj (Our Approach) endobj 45 0 obj << /S /GoTo /D (section.2.2) >> endobj 48 0 obj (Near-linear Time Min-cut Algorithm) endobj 49 0 obj << /S /GoTo /D (section.2.3) >> endobj 52 0 obj (Cactus Construction Algorithm) endobj 53 0 obj << /S /GoTo /D (subsection.2.3.1) >> endobj 56 0 obj (Listing minimal min-cuts of vertices) endobj 57 0 obj << /S /GoTo /D (subsection.2.3.2) >> endobj 60 0 obj (Labeling minimal min-cuts of vertices) endobj 61 0 obj << /S /GoTo /D (subsection.2.3.3) >> endobj 64 0 obj (Labeling second-smallest min-cuts of vertices) endobj 65 0 obj << /S /GoTo /D (subsection.2.3.4) >> endobj 68 0 obj (Minimal min-cuts of edges) endobj 69 0 obj << /S /GoTo /D (subsection.2.3.5) >> endobj 72 0 obj (Cactus construction from minimal min-cuts) endobj 73 0 obj << /S /GoTo /D (section.2.4) >> endobj 76 0 obj (Concluding Remarks) endobj 77 0 obj << /S /GoTo /D (section.2.5) >> endobj 80 0 obj (Notes) endobj 81 0 obj << /S /GoTo /D (chapter.3) >> endobj 84 0 obj (Cut Sparsification) endobj 85 0 obj << /S /GoTo /D (section.3.1) >> endobj 88 0 obj (Background) endobj 89 0 obj << /S /GoTo /D (subsection.3.1.1) >> endobj 92 0 obj (Connectivity Parameters) endobj 93 0 obj << /S /GoTo /D (subsection.3.1.2) >> endobj 96 0 obj (Edge Compression) endobj 97 0 obj << /S /GoTo /D (subsection.3.1.3) >> endobj 100 0 obj (History) endobj 101 0 obj << /S /GoTo /D (section.3.2) >> endobj 104 0 obj (Our Contributions) endobj 105 0 obj << /S /GoTo /D (subsection.3.2.1) >> endobj 108 0 obj (A General Sparsification Framework) endobj 109 0 obj << /S /GoTo /D (subsection.3.2.2) >> endobj 112 0 obj (Applications of the Sparsification Framework) endobj 113 0 obj << /S /GoTo /D (subsection.3.2.3) >> endobj 116 0 obj (Sparsification Algorithms) endobj 117 0 obj << /S /GoTo /D (section.3.3) >> endobj 120 0 obj (Modified Chernoff Bounds) endobj 121 0 obj << /S /GoTo /D (section.3.4) >> endobj 124 0 obj (Counting Cut Projections) endobj 125 0 obj << /S /GoTo /D (section.3.5) >> endobj 128 0 obj (The General Sparsification Framework) endobj 129 0 obj << /S /GoTo /D (section.3.6) >> endobj 132 0 obj (Sparsification by Edge Compression) endobj 133 0 obj << /S /GoTo /D (subsection.3.6.1) >> endobj 136 0 obj (Compression using Edge Connectivities) endobj 137 0 obj << /S /GoTo /D (subsection.3.6.2) >> endobj 140 0 obj (Compression using Edge Strengths) endobj 141 0 obj << /S /GoTo /D (subsection.3.6.3) >> endobj 144 0 obj (Compression using NI indices) endobj 145 0 obj << /S /GoTo /D (section.3.7) >> endobj 148 0 obj (Cut Sparsification Algorithm) endobj 149 0 obj << /S /GoTo /D (subsection.3.7.1) >> endobj 152 0 obj (Cut Preservation) endobj 153 0 obj << /S /GoTo /D (subsection.3.7.2) >> endobj 156 0 obj (Size of the sparsifier) endobj 157 0 obj << /S /GoTo /D (subsection.3.7.3) >> endobj 160 0 obj (Time complexity) endobj 161 0 obj << /S /GoTo /D (section.3.8) >> endobj 164 0 obj (Concluding Remarks) endobj 165 0 obj << /S /GoTo /D (section.3.9) >> endobj 168 0 obj (Notes) endobj 169 0 obj << /S /GoTo /D (part.2) >> endobj 172 0 obj (II Network Design) endobj 173 0 obj << /S /GoTo /D (chapter.4) >> endobj 176 0 obj (Online Steiner Tree and Related Problems) endobj 177 0 obj << /S /GoTo /D (section.4.1) >> endobj 180 0 obj (Background) endobj 181 0 obj << /S /GoTo /D (subsection.4.1.1) >> endobj 184 0 obj (Edge-weighted and Node-weighted Problems) endobj 185 0 obj << /S /GoTo /D (subsection.4.1.2) >> endobj 188 0 obj (The Online Model) endobj 189 0 obj << /S /GoTo /D (subsection.4.1.3) >> endobj 192 0 obj (Bi-criteria Approximation for Network Design Problems) endobj 193 0 obj << /S /GoTo /D (subsection.4.1.4) >> endobj 196 0 obj (History) endobj 197 0 obj << /S /GoTo /D (section.4.2) >> endobj 200 0 obj (Our Contributions) endobj 201 0 obj << /S /GoTo /D (section.4.3) >> endobj 204 0 obj (Online Node-weighted Steiner Tree) endobj 205 0 obj << /S /GoTo /D (section.4.4) >> endobj 208 0 obj (Online Group Steiner Forest) endobj 209 0 obj << /S /GoTo /D (subsection.4.4.1) >> endobj 212 0 obj (Online Group Steiner Forest on Trees) endobj 213 0 obj << /S /GoTo /D (subsection.4.4.2) >> endobj 216 0 obj (Online Node-weighted Group Steiner Forest) endobj 217 0 obj << /S /GoTo /D (subsection.4.4.3) >> endobj 220 0 obj (Online Edge-weighted Group Steiner Forest) endobj 221 0 obj << /S /GoTo /D (section.4.5) >> endobj 224 0 obj (Online Edge-weighted Single-Source Vertex Connectivity) endobj 225 0 obj << /S /GoTo /D (section.4.6) >> endobj 228 0 obj (Concluding Remarks) endobj 229 0 obj << /S /GoTo /D (section.4.7) >> endobj 232 0 obj (Notes) endobj 233 0 obj << /S /GoTo /D (chapter.5) >> endobj 236 0 obj (Network Activation Problems) endobj 237 0 obj << /S /GoTo /D (section.5.1) >> endobj 240 0 obj (Background) endobj 241 0 obj << /S /GoTo /D (section.5.2) >> endobj 244 0 obj (Our Contributions) endobj 245 0 obj << /S /GoTo /D (section.5.3) >> endobj 248 0 obj (Minimum Spanning Activation Tree) endobj 249 0 obj << /S /GoTo /D (section.5.4) >> endobj 252 0 obj (Minimum Steiner Activation Forest) endobj 253 0 obj << /S /GoTo /D (section.5.5) >> endobj 256 0 obj (Minimum Vertex-connected Activation Network with R=2) endobj 257 0 obj << /S /GoTo /D (subsection.5.5.1) >> endobj 260 0 obj (Minimum Leaf-weighted Subtree) endobj 261 0 obj << /S /GoTo /D (section.5.6) >> endobj 264 0 obj (Minimum Edge-connected Activation Network with R=2) endobj 265 0 obj << /S /GoTo /D (section.5.7) >> endobj 268 0 obj (Minimum Edge-connected Activation Network for Arbitrary R) endobj 269 0 obj << /S /GoTo /D (subsection.5.7.1) >> endobj 272 0 obj (Connection between MEAN and MDAN Problems) endobj 273 0 obj << /S /GoTo /D (subsection.5.7.2) >> endobj 276 0 obj (Installation Cost Optimization) endobj 277 0 obj << /S /GoTo /D (section.5.8) >> endobj 280 0 obj (Minimum Activation Path) endobj 281 0 obj << /S /GoTo /D (section.5.9) >> endobj 284 0 obj (Concluding Remarks) endobj 285 0 obj << /S /GoTo /D (section.5.10) >> endobj 288 0 obj (Notes) endobj 289 0 obj << /S /GoTo /D [290 0 R /Fit] >> endobj 292 0 obj << /Length 913 /Filter /FlateDecode >> stream xVKo8W(5/I$X)vDlp)*E;i9 mQ`{p7|]\dI%]e%$Hp0 oF50kKDlzF#7_}ݵ,zP?5&Z\!XY쀷LS˘,y)4 cލkqP/.AIF kQ K8hgoՃHrF~0ŘH,g,X19U[)awb\Qf0vnK%R: 12>gF#+Ft~