ABSTRACT
Contents 5.1 Introduction ................................................................................................................... 120
5.1.1 Coverage ..............................................................................................................121 5.1.2 Connectivity ....................................................................................................... 122 5.1.3 Cheapest Path ..................................................................................................... 122 5.1.4 Maximum Matching .......................................................................................... 122 5.1.5 Maximum Flow .................................................................................................. 122 5.1.6 Minimum Cost Flow .......................................................................................... 123
5.2 Preliminaries .................................................................................................................. 123 5.3 Coverage and Connectivity ............................................................................................ 124
5.3.1 Coverage ............................................................................................................. 124 5.3.1.1 Computational Complexity for k-CMI ................................................. 126 5.3.1.2 Approximation Results for k-CMI ........................................................ 127 5.3.1.3 Solvable Cases for k-CMI ..................................................................... 128 5.3.1.4 Unbounded CMI .................................................................................. 128
5.3.2 Connectivity ....................................................................................................... 130 5.3.2.1 Computational Complexity for Connectivity ........................................132
