پیچیدگی پارامتر بندی از مشکلات چندپخشی حداقل قدرت در شبکه های ad hoc بی سیم ☆

Power assignment in wireless ad hoc networks can be seen as a family of problems in which the task is to find in a given power requirement network a minimum power communication subnetwork that satisfies a given connectivity constraint. These problems have been extensively studied from the viewpoint of approximation, heuristic, linear programming, etc  . In this paper, we add a new facet by initiating a systematic parameterized complexity study of three types of power assignment problems related to multicast: Min-power Single-source hh-Multicast, Min-power Strongly Connected hh-Multicast and Min-power Multi-source hh-Multicast. We investigate their parameterized complexities with respect to the number of terminals and the number of senders. We show that a Min-power Single-source hh-Multicast is fixed-parameter tractable with respect to the number of terminals and achieve several parameterized hardness results.