论文标题
微型不对称连通性的参数化复杂性
Parameterized Complexity of Min-Power Asymmetric Connectivity
论文作者
论文摘要
我们研究了在无线传感器网络中具有应用的NP - 硬性问题Min-Power不对称连接（MINPAC）的参数化算法。鉴于有定向的电弧加权图，MinPac要求有牢固连接的跨度子图最小化的顶点成本。在这里，每个顶点的成本是其选定子图中最重的弧的重量。我们提供了线性时间算法，即在所谓的强制性子图中牢固连接的组件数量或基础无向图中的反馈边缘数量恒定的情况。与这些结果相辅相成，我们证明了问题在解决方案成本方面是W [2] - 即使在具有一个反馈弧和二元弧权重的受限图上也是如此。
We investigate parameterized algorithms for the NP-hard problem Min-Power Asymmetric Connectivity (MinPAC) that has applications in wireless sensor networks. Given a directed arc-weighted graph, MinPAC asks for a strongly connected spanning subgraph minimizing the summed vertex costs. Here, the cost of each vertex is the weight of its heaviest outgoing arc in the chosen subgraph. We present linear-time algorithms for the cases where the number of strongly connected components in a so-called obligatory subgraph or the feedback edge number in the underlying undirected graph is constant. Complementing these results, we prove that the problem is W[2]-hard with respect to the solution cost, even on restricted graphs with one feedback arc and binary arc weights.
