Partition on trees with supply and demand: Kernelization and algorithms
Partition on trees with supply and demand: Kernelization and algorithms
复制标题
根据供给和需求对树进行划分：核化和算法
DOI：
10.1016/j.tcs.2016.06.044
复制
发表时间：
2017
影响因子：
1.1
通讯作者：
Wenjun Li
中科院分区：
文献类型：
--
作者：
Mugang Lin;Qilong Feng;Jianer Chen;Wenjun Li
网络重构是配电网规划和运行中的一个重要研究课题。本文从参数化计算的角度研究了具有供给和需求的树上的划分问题。我们分析了供应节点和需求节点之间的关系，并给出了四个约简规则，这导致一个大小为O（k2）的核问题。基于分支技术，给出了一个运行时间为O ∞（2.828k）的参数化算法.
Network reconfiguration is an important research topic in the planning and operation of power distribution networks. In this paper, we study the partition problem on trees with supply and demand from parameterized computation perspective. We analyze the relationship between supply nodes and demand nodes, and give four reduction rules, which result in a kernel of size O (k 2) for the problem. Based on branching technique, a parameterized algorithm of running time O⁎(2.828 k) is presented.