Partition on trees with supply and demand: Kernelization and algorithms Academic Article uri icon

abstract

  • 2016 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(k2) for the problem. Based on branching technique, a parameterized algorithm of running time O(2.828k) is presented.

published proceedings

  • THEORETICAL COMPUTER SCIENCE

author list (cited authors)

  • Lin, M., Feng, Q., Chen, J., & Li, W.

citation count

  • 7

complete list of authors

  • Lin, Mugang||Feng, Qilong||Chen, Jianer||Li, Wenjun

publication date

  • January 2017