The Min-Power Multicast Problems in Wireless Ad Hoc Networks: A Parameterized View

摘要

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 h-Multicast, Min-power Strongly Connected h-Multicast and Min-power Multi-source h-Multicast. We investigate their parameterized complexities with respect to the number of terminals and the number of senders. We show that Min-power Single-source /i-Multicast is fixed-parameter tractable with respect to the number of terminals and achieve several parameterized hardness results.